У вас есть правильные локали на машине? Вы можете найти поддерживаемые локали, выполнив
$ less /usr/share/i18n/SUPPORTED
Локали, упомянутые в /var/lib/locales/supported.d/local, будут восстановлены при запуске
$ dpkg-reconfigure locales
В противном случае ваша проблема может быть вашим клиентом SSH. Если вы используете Putty, попробуйте следующее:
Перейдите в [Connection> Data] и измените строку «Terminal type» на «linux». Перейдите в [Window> Translation] и измените «Удаленный набор символов» на UTF-8.