$ sudo locale-gen "en_US.UTF-8"
$ sudo update-locale LC_ALL=en_US.UTF-8 LANG=en_US.UTF-8
It updates /etc/default/locale with provided values.
Now logout and log in (or even restart the machine).
Source: http://askubuntu.com/questions/162391/how-do-i-fix-my-locale-issue