I have an Ubuntu server 14.04 and got the message during system update:

?> sudo apt-get -y dist-upgrade
...
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = (unset),
LC_ALL = (unset),
LC_TIME = "en_US.UTF-8",
LC_MONETARY = "en_US.UTF-8",
LC_ADDRESS = "en_US.UTF-8",
LC_TELEPHONE = "en_US.UTF-8",
LC_NAME = "en_US.UTF-8",
LC_MEASUREMENT = "en_US.UTF-8",
LC_IDENTIFICATION = "en_US.UTF-8",
LC_NUMERIC = "en_US.UTF-8",
LC_PAPER = "en_US.UTF-8",
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
...


To solve this you will have to compile the locale definitions:

?> sudo locale-gen en_US en_US.UTF-8

and then reconfigure the locale setup:

?> sudo dpkg-reconfigure locales


Problem solved!