То, что сработало для меня в 12.10, было следующим:
apt-get install language-pack-en-base
Это было после того, как dpkg-reconfigure locales не дал никаких результатов.