У меня была такая проблема решение смешное.
Сделал: udo aptitude install console-cyrillic сконфигурировал все по русски, но при перезагрузки опять крякозябры. Решение простое, dpkg-reconfigure console-setup, настроил затем выкосил console-cyrillic. И все заработало как надо. Видимо вместе с console-cyrillic прилетели какие то кодировки.