I can't reproduce this on trunk (or 3.0 maint) on Gentoo Linux:

~/python/py3k>./python
Python 3.1b1+ (py3k:72816, May 21 2009, 22:01:55) 
[GCC 4.3.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import locale
[50411 refs]
>>> locale.getlocale()
('zh_TW', 'eucTW')
[50423 refs]
>>> help()

Welcome to Python 3.1!  This is the online help utility.

[...]

>>> locale.setlocale(locale.LC_ALL, '')
'zh_TW.eucTW'
[50462 refs]
>>> help()

Welcome to Python 3.1!  This is the online help utility.

[...]

Leon: you say ActivePython, which is a vendor distribution.  I think you
should report this bug to them, unless you can reproduce it using the
python.org python.