Error variables locales

Hola lo primero, un saludo caluroso a toda la comunidad de debian y en especial a la gente que se curra este portal que creo que puede ayudar mucho a la misma.
Mi pregunta es la siguiente, cada vez que instalo un paquete o desinstalo un paquete suele aparecerme este error. Creo que me aparece desde que me actualicé algunos paquetes de woody. El mensaje de error es el siguiente:

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = "es_ES",
LC_ALL = "es_ES",
LANG = "spanish"
are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

Pues, bien no se de donde puede venir ya que en el profile del root, esta puesta la linea export LANG=es_ES
Aparte, en el .bashrc están puestas las lineas LANGUAGE = "es_ES",LC_ALL = "es_ES", LANG = "spanish".
También en el /etc/locale.gen esta puesta la linea es_ES ISO-8859-1, para temas de castellanización (No se si tiene que ver con el resto).
Agradezco de antemano a la gente que se haya molestado en leer esta consulta, pueda o no ayudarme. Gracias.