I recently got this error on a new Ubuntu 9.10 system when installing a package.

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = (unset),
LC_ALL = (unset),
LANG = “en_AU.UTF-8”
are supported and installed on your system.
perl: warning: Falling back to the standard locale (“C”).

An easy way to fix it is to reinstall your language pack.

sudo apt-get install –reinstall language-pack-en