perl locale warnings

On a fresh install of Ubuntu server 12.04 LTS, the first thing I type in a terminal after a clean installation and the very first boot of the OS:

root@ip-10-228-91-223:~# perl
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
 LANGUAGE = (unset),
 LC_ALL = (unset),
 LC_PAPER = "en_DK.UTF-8",
 LC_ADDRESS = "en_DK.UTF-8",
 LC_MONETARY = "en_DK.UTF-8",
 LC_NUMERIC = "en_DK.UTF-8",
 LC_TELEPHONE = "en_DK.UTF-8",
 LC_IDENTIFICATION = "en_DK.UTF-8",
 LC_MEASUREMENT = "en_DK.UTF-8",
 LC_TIME = "en_DK.UTF-8",
 LC_NAME = "en_DK.UTF-8",
 LANG = "en_US.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
^C
root@ip-10-228-91-223:~#

I have had this bug happen to me at least 20+ separate installation since the beginning of this year (it was never an issue before that) in both Ubuntu and Debian. It is about time something is done about it so I won't have to "fix" this on every new install of Ubuntu.

root@ip-10-228-91-223:~# lsb_release -rd
Description: Ubuntu 12.04 LTS
Release: 12.04

Workarounds are plentiful and are not sought after. A permanent fix of this bug is requested instead.