Debian Lenny locales problem

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 [...]

Continue reading about Debian Lenny locales problem