To solve this, first try using the command:
sudo locale-gen
if this does not work check with locale -a the locale you actually got on your system and make sure you have the locale in UTF-8 encoding for every language on your system, something like this:
$ locale -a
C
C.UTF-8
en_AG
en_AG.utf8
en_AU.utf8
en_BW.utf8
en_CA.utf8
en_DK.utf8
en_GB.utf8
en_HK.utf8
en_IE.utf8
en_IN
en_IN.utf8
en_NG
en_NG.utf8
en_NZ.utf8
en_PH.utf8
en_SG.utf8
en_US.utf8
en_ZA.utf8
en_ZM
en_ZM.utf8
en_ZW.utf8
POSIX
pt_BR.utf8
pt_PT.utf8
And use the following command to generate it:
localedef -v -c -i en_US -f UTF-8 en_US.UTF-8
(It's case sensitive as far as I remember, you actually have to use the resulting locale string literally.)
If you continue to get error messages and you are accessing a remote server, check if the default locale setting on your machine is supported by the remote box.
You can check the default locale setting with:
cat /etc/default/locale
which in my case returned:
LANG="en_US.UTF-8"
In my case the default locale on my laptop was en_US.UTF-8, but the server was using en_GB.UTF-8 only. I solved this by adding en_US.UTF-8 to /etc/default/locale (via "dpkg-reconfigure locales").