How to solve "perl: warning: Setting locale failed." in debian and ubuntu

This annoying message in debian 5 has a simple solution:

dpkg-reconfigure locales

And then choose your encoding of choice, e.g. en_US Utf8

Or, in Ubuntu 9.10 or 10.04:

apt-get install --reinstall language-pack-en