How do I fix my locale issue?

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.