Python locale error: unsupported locale setting

Why do I get the following error when doing this in python:

>>> import locale

>>> print str( locale.getlocale() )

(None, None)

>>> locale.setlocale(locale.LC_ALL, 'de_DE')

Traceback (most recent call last):

  File "", line 1, in

  File "/usr/lib/python2.7/locale.py", line 531, in setlocale

    return _setlocale(category, locale)

locale.Error: unsupported locale setting

This works with other locales like fr or nl as well. I'm using Ubuntu 11.04.

Update: Doing the following did not yield anything:

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