A pouco mais de duas semanas, estava tendo um problema, com um servidor, que sempre me mostrava o erro:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
	LANGUAGE = "en_US:",
	LC_ALL = (unset),
	LC_MESSAGES = "pt_BR.UTF-8",
	LC_COLLATE = "pt_BR.UTF-8",
	LC_CTYPE = "pt_BR.UTF-8",
	LANG = "en_US.UTF-8"
    are supported and installed on your system.

E finalmente, encontrei a solução. O erro não causava nem problema de utilização, mas atrapalhava a visualização no terminal. (Imaginem como era legal, quando eu acessava pelo celular.

Resolução

Primeiro defini as variáveis do sistema, para as do idioma que desejava.

export LANGUAGE=en_US.UTF-8
export LANG=en_US.UTF-8
export LC_ALL=en_US.UTF-8

Depois geramos o arquivo de language desejado:

locale-gen en_US.UTF-8

E para finalizar reconfiguramos o pacote de locales:

dpkg-reconfigure locales

Caso o erro continue mande reinstalar o pacote de locales:

apt-get install –reinstall locales

Uma solução, muito, muito, muito fácil. Mas tive uma grande dificuldade, pois a maioria dos fóruns e tutoriais que eu achava, apenas me diziam os dois últimos passos.

Atualização em 26 de outubro de 2012:

Para facilitar criei um scriptque é só rodar, e pronto ta consertado. locales.sh