sudo apt-get purge locales
then:
sudo aptitude install locales
and then
sudo dpkg-reconfigure locales
This rids the system of locales, then re-installs locales and downgrades libc6 from 2.19 to 2.13 which is the issue. Then configures locales again.