Todas las soluciones que he ido probando a lo largo del tiempo han terminado por dejar de ser validas, pero a fecha de Febrero de 2010, esta receta funcionaba.
Si nos encontramos con los errores:

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 de Diciembre 2011
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 Marzo 2016

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"