Не знам дали няма да има странични ефекти, но се получи, както са го описали в линка.
Добавих в:
sudo nano /etc/initramfs-tools/initramfs.conf
ред:
FRAMEBUFFER=Y
После ако ги няма инсталирани /при мен ги имаше/
sudo apt-get install console-setup
sudo apt-get install console-setup-linux
махнах Console-cyrillic
sudo apt-get remove console-cyrillic
редактирах
sudo nano /etc/default/console-setup
за да придобие следния вид:
CHARMAP="UTF-8"
CODESET="CyrSlav"
FONTFACE="VGA"
FONTSIZE="16" // не 8Х16

после изпълнявам:
sudo setupcon --save
sudo gunzip -k /etc/console-setup/CyrSlav-VGA16.psf.gz
sudo update-initramfs -u

Рестарт и си получих кирилицата.
Дано бъде полезно на някого

За да не стане объркване искам да си призная, че Линукс не ми е сила

Изчетох доста нещо и направих няколко настройки:
в
/etc/initramfs-tools/initramfs.conf
добавих ред:
FRAMEBUFFER=Y
после пуснах както му се полага:
sudo update-initramfs -u
после пуснах и
sudo dpkg-reconfigure console-setup
и тук стана интересно. Тъй като не четях написаното на кирилица му потвърждавах настройките по подразбиране.
След последната обаче то си изпълни отново update-initramfs само и моментално шрифта се смени и надписите на кирилица се появиха. До тук всичко наред, обаче след рестарт пак всичко е омазано.
Пуснах пак sudo dpkg-reconfigure console-setup за да видя кирилицата и после dpkg-reconfigure console-cyrillic за да мога да чета.
Направи ми впечатление, че след "Желаете ли конзолата да бъде кирилизирана след старт на системата" - ОК се появи съобщение:
update-rc.d: warning: start and stop actions are no longer supported; falling back to defaults.
И след рестарт пак няма кирилица.
Някъде видях предложение за добавяне на sudo /etc/init.d/console-cyrillic start в /etc/rc.local но пак без успех

PS: След още търсене накрая разбрах, че в 15.04 е сменен начинът на буутване на системата и всичко описано до тук, което е работило за версии до 15.04 вече не работи. Единствено тук: http://my-easy-linux.blogspot.com/2015/05/ubuntu-server-15.html намерих, че някой е успял да подкара кирилицата в конзолата по малко странен според мен начин, но утре ще пробвам дали ще се получи.

Благодаря за отговорите.
Инсталирах отново трите предложени шрифта. Dejavu-core го имаше, но го инсталирах отново.
Никаква промяна. Пуснах sudo dpkg-reconfigure console-cyrillic но в диалога всичко е на споменатите квадратчета.
Все пак мисля, че се ориентирах до някъде и в момента файла /etc/console-cyrillic ми изглежда така:

style uni
size 14
encoding utf-8
layout by
options caps_toggle win_switch
ttys /dev/tty[1-6]

Здравейте,
От два дни се мъча с една инсталация на Ubuntu server х86 15.04.
При инсталацията го локализирах в България, зададох му и формати на български.
Проблема ми е , че в шела доста от символите ми излизат като бели квадратчета и това са символите при диалогови съобщения от системата. Примерно при apt-get update в началото на реда излизат такива символи, после линковете си се четат и накрая съобщението в края на командата си е пак на квадратчета.
Проверих си локализацията и навсякъде е bg_BG.UTF-8.
Не съм инсталирал desktop на машината и по принцип не го искам.

Ще се радвам ако някой има идея как да накарам белите квадратни символи да станат разбираеми. Взех да си мисля, че липсва шрифт, но не зная кой. Имам една машина с ubuntu server 13.1 и там нямам такива проблеми.