Problema de codificação de caracteres com a instalação do meu linux?

Question

Acabei de instalar o Ubuntu 12.04.4 64 bits, tudo parecia estar ok, quando comecei a trabalhar no console notei:

• que eu não consegui digitar alguns caracteres acentuados no console, por exemplo, se eu tentasse digitar é eu teria um ?
• Que nem a saída ls ou qualquer outro comando unix exibiria esses caracteres adequadamente.
• ANSIX3.4-1968 apareceu como codificação de caracteres padrão no terminal, portanto:
  • Alterei a codificação de caracteres para UTF-8 na opção Definir codificação de caracteres no menu Terminal. Eu posso digitar esses caracteres especiais corretamente, mas não posso obter outros comandos para saída de forma correta. E eu tenho que mudar isso toda vez que eu abro um novo console.

Quando eu instalo qualquer coisa, vejo isso entre as saídas e as informações de log:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
    LANGUAGE = "en_US:en",
    LC_ALL = (unset),
    LC_TIME = "es_MX.UTF-8",
    LC_MONETARY = "es_MX.UTF-8",
    LC_ADDRESS = "es_MX.UTF-8",
    LC_TELEPHONE = "es_MX.UTF-8",
    LC_NAME = "es_MX.UTF-8",
    LC_MEASUREMENT = "es_MX.UTF-8",
    LC_IDENTIFICATION = "es_MX.UTF-8",
    LC_NUMERIC = "es_MX.UTF-8",
    LC_PAPER = "es_MX.UTF-8",
    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_ALL to default locale: No such file or directory

Além disso, se eu fizer um erro de digitação em qualquer comando do console, obtenho:

Sorry, command-not-found has crashed! Please file a bug report at:
https://bugs.launchpad.net/command-not-found/+filebug
Please include the following information with the report:

command-not-found version: 0.2.44

Minhas configurações na instalação eram apenas em inglês e espanhol. O que poderia ter acontecido? E como posso corrigi-lo permanentemente ?