Recently I have been facing some issues with locales in Debian and Ubuntu based Xen based virtual servers. These typically appear while running the man command and apt-get or dpkg commands.

The message typically are of the kinds:

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.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

The solution for this was simple:

$ sudo apt-get install locales
$ sudo dpkg-reconfigure locales

In a more recent experience on one of the Ubuntu Jaunty (9.04) builds, while I ran the above dpkg-reconfigure command the error messages were:

$ sudo dpkg-reconfigure locales
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = "en_US:en",
	LC_ALL = (unset),
	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_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

In order to fix them, see below:

$ sudo locale-gen en_US.UTF-8
Generating locales...
  en_US.UTF-8... up-to-date
Generation complete.
$ sudo /usr/sbin/update-locale LANG=en_US.UTF-8

For the time being these should be enough to solve your problems. If time permits perhaps I will write in detail about how these locales work and what all basic utilities deal with them.