http://stackoverflow.com/questions/2499794/how-can-i-fix-a-locale-warning-from-perl

on Debian after much searching this did the trick.

first:

sudo apt-get purge locales

then:

sudo aptitude install locales

and the famous:

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.