Eu tive esse problema exato. Eu consertei adicionando export LANG="en_GB.utf8"
a ~/.bashrc
e depois desconectei para reiniciar minha sessão com a janela X.
Use locale -a | grep -i utf8
da linha de comando para obter uma lista de localidades com suporte a UTF-8.
Acho que o problema é que o Gnome Terminal desativará automaticamente o suporte a UTF-8 se ele não detectá-lo em suas variáveis de ambiente local.