How to fix locale settings in Debian squeeze

I occasionally get locale errors and I've tried to run dpkg-reconfigure locales to fix the problem. Here's the output:

:~$ sudo dpkg-reconfigure locales
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
Generating locales (this might take a while)...
  en_US.UTF-8... done
Generation complete.
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_CTYPE = "UTF-8",
    LANG = "C"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

I looked for /usr/bin/locale but it doesn't exist on my system. Do I need to create it? What do I put in there?

Also I found a related question that says the cause of his problem was in the sshd_config file. The file had the following entry:

AcceptEnv LANG LC_*

I'm mainly concerned that it may cause problems for my VPS, otherwise if it's nothing major I'll be happy to ignore the problem. What should I do? thanks!