primeiro:
sudo apt-get purge locales
então:
sudo aptitude install locales
e o famoso:
sudo dpkg-reconfigure locales
Isso libera o sistema de localidades e, em seguida, reinstala os códigos de idioma e reduz a versão libc6 de 2.19 para 2.13, que é o problema. Em seguida, configura as localidades novamente.