I've had similar problem on my ubuntu server (FlexiScale) and searched for a solution for a while but could not find anything suitable... Still not sure if what I did is the "right way", but it seems to work.
The warning I was seeing was:
bash: warning: setlocale: LC_CTYPE: cannot change locale (UTF-8)
To make sure the locales are up-to-date I did this (not sure if this was neccessary):
# locale-gen --purge
locale on my system was showing
LC_CTYPE="UTF-8" which didn't look right to me, so I've changed my
/etc/default/locale to look like this:
(I've added the second line.) After re-login the warnings were gone.