Баг существует еще с древних времен, лечится тоже по-разному. В первую очередь нужно выполнить
sudo dpkg-reconfigure console-setup
Там выбрать UTF-8 и в конце поменять шрифт на Terminus или TerminusBold После чего при ручном выполнении setupcon всё придет в норму. Раньше, достаточно было добавить setupcon в /etc/rc.local, но т.к. новая Ubuntu уже на systemd, то этот способ не работает. Работает добавление в файл
sudo gedit /lib/systemd/system/console-setup.service
в самый конец дописать
ExecStart=/bin/setupcon
Теперь после перезагрузки кириллица в консоли будет работать сразу
UPD для Ubuntu 16.04
После выполнения
dpkg-reconfigure console-setup
"ExecStart=/bin/setupcon" само появилось в
/lib/systemd/system/console-setup.service