Uma coisa que você pode tentar é o seguinte comando para definir o local do console:
sudo dpkg-reconfigure console-setup
Verifique se a codificação está definida como UTF-8, em vez de ISO-8859- * ou outra coisa. Espero que o seu problema seja tão simples assim.