I have a fresh ubuntu 12.04 installation. When i connect to my remote server i got errors like this:

~$ ssh example.com sudo aptitude upgrade
...
Traceback (most recent call last):
  File "/usr/bin/apt-listchanges", line 33, in <module>
    from ALChacks import *
  File "/usr/share/apt-listchanges/ALChacks.py", line 32, in <module>
    sys.stderr.write(_("Can't set locale; make sure $LC_* and $LANG are correct!\n"))
NameError: name '_' is not defined
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_TIME = "de_DE.UTF-8",
    LC_MONETARY = "de_DE.UTF-8",
    LC_ADDRESS = "de_DE.UTF-8",
    LC_TELEPHONE = "de_DE.UTF-8",
    LC_NAME = "de_DE.UTF-8",
    LC_MEASUREMENT = "de_DE.UTF-8",
    LC_IDENTIFICATION = "de_DE.UTF-8",
    LC_NUMERIC = "de_DE.UTF-8",
    LC_PAPER = "de_DE.UTF-8",
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_ALL to default locale: No such file or directory
No packages will be installed, upgraded, or removed.
0 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B of archives. After unpacking 0 B will be used.
...

I don't have this problem when i connect from an older ubuntu installation. This is output from my ubuntu 12.04 installation, LANG and LANGUAGE are set

$ locale
LANG=de_DE.UTF-8
LANGUAGE=de_DE:en_GB:en
LC_CTYPE="de_DE.UTF-8"
LC_NUMERIC=de_DE.UTF-8
LC_TIME=de_DE.UTF-8
LC_COLLATE="de_DE.UTF-8"
LC_MONETARY=de_DE.UTF-8
LC_MESSAGES="de_DE.UTF-8"
LC_PAPER=de_DE.UTF-8
LC_NAME=de_DE.UTF-8
LC_ADDRESS=de_DE.UTF-8
LC_TELEPHONE=de_DE.UTF-8
LC_MEASUREMENT=de_DE.UTF-8
LC_IDENTIFICATION=de_DE.UTF-8
LC_ALL=

Does anybody know what has changed in ubuntu to get this error message on remote servers?