Você pode tentar reconfigurar o pacote locales, que deve solicitar que você defina a localidade do sistema.
dpkg-reconfigure locales
Você também pode executar o aptitude com uma localidade específica para solucionar problemas.
LANG=en_US.UTF-8 aptitude