Debian 5.0 - can't set the locale

Hello. New Linode user here, and very very happy about it so far.

I've setup a Debian 5.0 server using the linode configuration profile. I believe I've run into this bug: http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=494989 which indicates it's been fixed for a little while now, however, after installing all updates available I still have the issue.

Here's what I'm seeing:

billl@li62-68:/$ sudo apt-get install mc
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  libglib2.0-0 libglib2.0-data libgpm2
Suggested packages:
  gpm zip unzip bzip2 links w3m lynx arj xpdf dbview odt2txt
The following NEW packages will be installed:
  libglib2.0-0 libglib2.0-data libgpm2 mc
0 upgraded, 4 newly installed, 0 to remove and 0 not upgraded.
Need to get 3631kB of archives.
After this operation, 11.7MB of additional disk space will be used.
Do you want to continue [Y/n]? y
Get:1 http://mirror.cc.columbia.edu lenny/main libgpm2 1.20.4-3.1 [33.8kB]
Get:2 http://mirror.cc.columbia.edu lenny/main libglib2.0-0 2.16.6-1+lenny1 [757kB]
Get:3 http://mirror.cc.columbia.edu lenny/main libglib2.0-data 2.16.6-1+lenny1 [699kB]
Get:4 http://mirror.cc.columbia.edu lenny/main mc 2:4.6.2~git20080311-4 [2140kB]
Fetched 3631kB in 0s (6443kB/s)
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    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_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory
Selecting previously deselected package libgpm2.
(Reading database ... 10964 files and directories currently installed.)
Unpacking libgpm2 (from .../libgpm2_1.20.4-3.1_i386.deb) ...
Selecting previously deselected package libglib2.0-0.
Unpacking libglib2.0-0 (from .../libglib2.0-0_2.16.6-1+lenny1_i386.deb) ...
Selecting previously deselected package libglib2.0-data.
Unpacking libglib2.0-data (from .../libglib2.0-data_2.16.6-1+lenny1_all.deb) ...
Selecting previously deselected package mc.
Unpacking mc (from .../mc_2%3a4.6.2~git20080311-4_i386.deb) ...
Processing triggers for man-db ...
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
/usr/bin/mandb: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
manconv: can't set the locale; make sure $LC_* and $LANG are correct
Setting up libgpm2 (1.20.4-3.1) ...
Setting up libglib2.0-0 (2.16.6-1+lenny1) ...
Setting up libglib2.0-data (2.16.6-1+lenny1) ...
Setting up mc (2:4.6.2~git20080311-4) ...
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LANG = "en_US.UTF-8"
    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),
    LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
billl@li62-68:/$

Google finds various people with various solutions to the problem, but they all seem to be pretty random. (or else my google fu has failed me this late night)

Any thoughts or pointers? TIA