Re-configuring the locales package, which should ask you to set your system locale.
dpkg-reconfigure locales
Also,
Run aptitude with a specific locale, for troubleshooting.
LANG=en_US.UTF-8 aptitude
Manually
Edit the file /etc/locale.gen and add your locale settings (one set per line), e.g.:
de_DE.UTF-8 UTF-8
de_DE ISO-8859-1
de_DE@euro ISO-8859-15
de_DE ISO-8859-1
de_DE@euro ISO-8859-15
The supported locales are listed in /usr/share/i18n/SUPPORTED.
Run the command locale-gen
Run the command locale -a to verify the list of available locales; note that the spellings change.
If you’ve upgraded to Lenny and you have leftover LANG=… content in /etc/environment, you should comment it out.
To use the new settings with your programs, log out and back in.