A continuación os dejo una serie de soluciones que me han ido funcionando históricamente para resolver problemas de locale: LC_TYPE, LC_MESSAGES, LC_ALL. 

Actualizado 2019 – Incluyo una forma de solucionar el error de locale en Raspbian Buster.

Solución a error de locale original de 2009:

locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

Podemos probar a solucionarlo con:

localedef -i en_US -c -f UTF-8 en_US.UTF-8

Actualizacion 2011: Solucionar errores de locale en Debian

Me he encontrado en una maquina con el siguiente error:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
        LANGUAGE = (unset),
        LC_ALL = (unset),
        LC_CTYPE = "en_US.UTF-8",
        LC_COLLATE = "en_US.UTF-8",
        LC_MESSAGES = "en_US.UTF-8",
        LANG = "es_ES.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

En este caso, la solucion que explicaba arriba en Febrero de 2010 no sirve, pero esto me ayudo a arreglar el problema.

export LANGUAGE=en_US.UTF-8
export LANG=en_US.UTF-8
export LC_ALL=en_US.UTF-8
locale-gen en_US.UTF-8
dpkg-reconfigure locales

Actualizacion 2016: Solucionar error locale en Ubuntu Server

Otra solucion que me ha funcionado hoy mismo en un Ubuntu Server 15.10 ha sido añadir la siguiente linea a /etc/environment

LC_ALL="en_US.UTF-8"

Actualización 2019: Solucionar error locale en Raspbian Buster

Me encuentro con que al cambiar la localización en Raspbian me sale el siguiente mensaje:

perl: warning: Please check that your locale settings:
    LANGUAGE = (unset),
    LC_ALL = (unset),
    LC_TIME = "es_ES.UTF-8",
    LC_MONETARY = "es_ES.UTF-8",
    LC_ADDRESS = "es_ES.UTF-8",
    LC_TELEPHONE = "es_ES.UTF-8",
    LC_NAME = "es_ES.UTF-8",
    LC_MEASUREMENT = "es_ES.UTF-8",
    LC_IDENTIFICATION = "es_ES.UTF-8",
    LC_NUMERIC = "es_ES.UTF-8",
    LC_PAPER = "es_ES.UTF-8",
    LANG = "C"
    are supported and installed on your system.

Para solucionarlo he hecho:

root@raspi:~# export LC_ALL="en_US.UTF-8"
root@raspi:~# LC_ALL="en_US.UTF-8" dpkg-reconfigure locales
 Generating locales (this might take a while)…
   en_US.UTF-8…
done
 Generation complete.

Se que resulta redundante el export, pero lo copio tal cual me ha funcionado :)