Cómo cambiar locales en debian 7?

Vamos a ver. Tengo un servidor virtual en Strato. Es. Es una debian 7. La verdad es que estoy harto de trabajar en debian, pero me ha surgido un problema. Tengo que hacer una web en aleman y hay enlaces que llevan äöü como caracteres. Esos enlaces, obviamente, no funcionan. Sin problema, cambio las locales y ya está. Pues no hay manera. Ejecuto dpkg-reconfigure locales, elijo de_DE.UTF8, quito es_ES.UTF8, selecciono de_DE. UTF8 y me dice que ok. Salgo y vuelvo a entrar y me dice que no puede cambiar las locales. Ejecuto locale y me sale todo es_ES. UTF8 a pesar de que en /etc/locale.gen esta solo descomentado de_DE. UTF8.

Me da que pensar que es porque accedo vía putty y hay algo que configurar ahí, pero no consigo verlo y los warnings en la consola me salen es español.