Здравствуйте.

console-cyrillic установлен. Чё ему нужно?
Кстати на ubuntu-13.10-server та же хрень. Хотя это сервер, но всё же, в Grub-меню знаками вопроса кирилица.

Загрузка нормальная.
И даже нет стандартной надписи при загрузке "Starting load fallback graphics devices [fail]".

Далее, по ходу, в /etc/default/grub вставил:
GRUB_CMDLINE_LINUX_DEFAULT="vga=791"
чтоб нормальными шрифтами отчёт загрузки выводил. В начале выскакивает строка начинающаяся с vga=791 deprecated... остальное прочесть не успеваю(мгновенно исчезает), далее нормально грузится.