Recently I bumped in a Debian Lenny locales problem,  on some amd64 cluster inside the cloud, during apt-get operations the system complains continuously about wrong or missing locales with messages like this:

perl: warning: Setting locale failed. perl: warning: Please check that your locale settings: LANGUAGE = (unset), LC_ALL = (unset), LANG = "en_US.UTF-8" are supported and installed on your system.

or like this:

manconv: can't set the locale; make sure $LC_* and $LANG are correct

The issue was fixed using this method,  reinstalling and regenerating the locales on the system, to avoid dependencies I used the following packages as a "bridge":

~# apt-get install belocs-locales-bin belocs-locales-data ~# locale-gen ~# dpkg-reconfigure locales

After issuing the command dpkg-reconfigure locales select the locales you need from the list and you should be done.