¿Por qué recibo el siguiente error al hacer esto en Python:

>>> import locale
>>> print str( locale.getlocale() )
(None, None)
>>> locale.setlocale(locale.LC_ALL, 'de_DE')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.7/locale.py", line 531, in setlocale
    return _setlocale(category, locale)
locale.Error: unsupported locale setting

Esto funciona con otras configuraciones regionales como fr o nl también. Estoy usando Ubuntu 11.04.

Actualización: Hacer lo siguiente no produjo nada:

dpkg-reconfigure locales
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = (unset)
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory