Eu tive o mesmo problema após a atualização do Ubuntu 15.10. Eu precisava reconfigurar meus locais.
Antes de fazer isso: Lembre-se que você volta para a GUI ("tela normal") pressionando Ctrl + Alt + F7
Abra o Emulador de texto e terminal (sem GUI)
Pressione: Ctrl + Alt + F1
Reconfigurar localidades
$ sudo dpkg-reconfigure locales
$ sudo locale-gen "en_US.UTF-8"
$ sudo localectl set-locale LANG="en_US.UTF-8"
Confirme o resultado
$ locale
LANG=en_US.UTF-8
LANGUAGE=en_US:en
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC=en_US.UTF-8
LC_TIME=en_US.UTF-8
LC_COLLATE="en_US.UTF-8"
LC_MONETARY=en_US.UTF-8
LC_MESSAGES="en_US.UTF-8"
LC_PAPER=en_US.UTF-8
LC_NAME=en_US.UTF-8
LC_ADDRESS=en_US.UTF-8
LC_TELEPHONE=en_US.UTF-8
LC_MEASUREMENT=en_US.UTF-8
LC_IDENTIFICATION=en_US.UTF-8
LC_ALL=
e
$ locale -a
C
C.UTF-8
en_US.utf8
POSIX
Mudar para a GUI
Pressione: Ctrl + Alt + F7
O terminal agora deve funcionar novamente. Você pode ter que reiniciar.