Рекомендую выполнить следующую команду:
$ LANG=C sudo dpkg-reconfigure console-setup
Далее (помимо прочих параметров) следует выбрать кодировку консоли - UTF-8 и шрифт, который содержит кириллицу, например, . combined - latin; slavic cyrillic или # cyrillic