Cannot set LC_ALL to default locale

[NoOp]

While fooling around with installing & uninstalling OpenOffice I made
the stupid mistake of doing an OOo install from the Edgy (Main)
repository. Although I've uninstalled that version since then I get the
following:

~$ locale
locale: Cannot set LC_ALL to default locale: No such file or directory
LANG=en_US.UTF-8
LANGUAGE=en_US.UTF-8
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=en_US.UTF-8

My system is:

Ubuntu: Dapper 6.061 LTS
Kernel: 2.6.15-27-386
GNOME Version: 2.14.3 - Ubuntu (2006-07-31)
GCC Version: 4.0.3 - i486-linux-gnu
Xorg Version: 7.0.0

Any ideas on what I need to uninstall/reinstall to get rid of the
locale: Cannot set LC_ALL to default locale: No such file or directory
error?

I've done the standard "Google" approach and have tried various
suggestions from the Ubuntu forums, linux forums etc., but still cannot
fix the problem. i.e.,
 dpkg-reconfigure locales
 uninstall & reinstall localeconf
etc.

If I attempt to deinstall locales I get:

> $ sudo apt-get remove locales
> Password:
> Reading package lists... Done
> Building dependency tree... Done
> Some packages could not be installed. This may mean that you have
> requested an impossible situation or if you are using the unstable
> distribution that some required packages have not yet been created
> or been moved out of Incoming.
> 
> Since you only requested a single operation it is extremely likely that
> the package is simply not installable and a bug report against
> that package should be filed.
> The following information may help to resolve the situation:
> 
> The following packages have unmet dependencies:
>   libc6: Depends: locales (>= 2.3.11)
> E: Broken packages

The version of locales that I have installed is 2.3.18

so I'm guessing that the problem is perhaps with the libc6 that the Edgy
OOo package installed. Unfortunately I can't seem to figure out how to
revert back to the Dapper libc6. I've tried to reinstall libc6 via
Synaptics as well as apt-get.

The problem itself doesn't seem to affect anything that I can tell so
far, but whenever I do an apt-get install or dpkg install I keep getting
the perl error warnings.