Problem with locale settings

Had this problem with previous server and was unable to solve it no matter how many websites and manuals I read. Apart from that, server performed well, uptime 263 days.

Am in the process of installing a new Linode512, Ubuntu 12.10 32 bit (in London) and I got this warning already several times (whith apt-get upgrade, adduser, dpkg-reconfigure tzdata, ….):
> perl: warning: Setting locale failed.

perl: warning: Please check that your locale settings:

LANGUAGE = (unset),

LC_ALL = (unset),

LC_CTYPE = "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_ALL to default locale: No such file or directory

/usr/bin/locale: Cannot set LC_CTYPE to default locale: No such file or directory

/usr/bin/locale: Cannot set LC_ALL to default locale: No such file or directory
How do I get it right this time?

Thanx