How do I fix my locale issue?

I am getting this message every time I do something like starting or stopping a service.

perl: warning: Setting locale failed.   
perl: warning: Please check that your locale settings:   
        LANGUAGE = "en_US:en",   
        LC_ALL = (unset),   
        LC_MESSAGES = "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   
(Reading database ... 21173 files and directories currently installed.)  
Removing bind9 ...  
 * Stopping domain name service... bind9                                        [ OK ]
Processing triggers for man-db ...   
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   

How do I fix this error ?

First run locale to list what locales currently defined for the current user account:

$ locale
LANG=C
LANGUAGE=
LC_CTYPE=fi_FI.UTF-8
LC_NUMERIC="C"
LC_TIME="C"
LC_COLLATE=fi_FI.UTF-8
LC_MONETARY="C"
LC_MESSAGES=fi_FI.UTF-8
LC_PAPER="C"
LC_NAME="C"
LC_ADDRESS="C"
LC_TELEPHONE="C"
LC_MEASUREMENT="C"
LC_IDENTIFICATION="C"
LC_ALL=

Then generate the missing locale and reconfigure locales to take notice:

$ sudo locale-gen "en_US.UTF-8"
Generating locales...
  en_US.UTF-8... done
Generation complete.

$ sudo dpkg-reconfigure locales
Generating locales...
  en_US.UTF-8... up-to-date
Generation complete.

Now you will not see any errors anymore!

Nothing suggested above worked in my case (Ubuntu Server 12.04LTS). What finally helped was putting to the file /etc/environment:

LC_ALL=en_US.UTF-8
LANG=en_US.UTF-8

For some reason it was missing. The outputs for locale and other commands appeared like the variables were properly defined. In other words don't take for granted all the basic stuff is declared where it should be declared.

They should disappear after issuing:

sudo locale-gen en_US en_US.UTF-8
sudo dpkg-reconfigure locales 

dpkg-reconfigure reconfigures packages after they have already been installed. Pass it the names of a package or packages to reconfigure. It will ask configuration questions, much like when the package was first installed.

Just add the following to your .bashrc file (assuming you're using bash)

export LC_ALL="en_US.UTF-8"