Tente digitar a seguinte linha de comando no console:
sudo dpkg-reconfigure locales
Na tela de configuração, escolha a codificação desejada. Você pode inclusive deixar o UTF-8 marcado, mas lembre-se de que na próxima tela, quando você for questionado sobre qual será a codificação padrão, você deve escolher a codificação desejada, no caso ISO-8859-1.