console-cyrillic и прочие reconfigure модифицируют файл /etc/default/console-setup Посмотрите там параметры в соответсвии с указанными в этой ветке. НО
Но причина то не внем как у меня оказалось, а в разрешении экрана консоли, который редактируется /etc/default/grub (спасибо Schneider) У меня лично все заработало, когда я закоментировал строчку с разрешением экрана.