Собственно проблема нарисовалась после автоматического апдейта убунты до версии 12.04. После перезагрузки компа увидел на экране примерно такое изображение: 
Топтание кнопки автоматической подствойки параментров монитора не помогло. Как выяснилось, на некоторых мониторах даже это не отображается. Grub по умолчанию видимо пытается самостоятельно определить разрешение монитора и ничего хорошего из этого не получается.
Короче, решается эта проблема просто. Правим конфиг /boot/grub/custom.cfg
Находим и раскоментируем строку
#GRUB_GFXMODE=640×480
Теперь заглянем в описание этого параметра:
GRUB_GFXMODE=640×480 - этот пункт отвечает за разрешение графического меню GRUB2. Данный параметр предоставляет разрешение, которое поддерживается видеокартой пользователя (например: 640×480, 800×600, 1024×768, 1600×1200 — для соотношения сторон 4:3. И 640×400, 800×500, 1024×640, 1280×800, 1680×1050 — для широкоформатных мониторов с соотношением сторон 16:10). Настройки применимы только для меню загрузки. Так же у нас есть возможность увидеть все доступные разрешения для экрана из меню GRUB2. Для этого, находясь в меню, жмем «с», затем в строке grub> пишем vbeinfo.
Если строка GRUB_GFXMODE=640×480 закомментирована или выбранное разрешение недоступно, тогда GRUB2 использует настройки по умолчанию, определенные скриптом /etc/grub.d/00_header.
Отлично, значит для моего монитора эта строка будет выглядеть так:
GRUB_GFXMODE=800x600x32,800x600x24,800×600
Третья цифра указывает битность изображения. Параметров как видите можно указывать несколько, через запятую. В этом случае загрузчик попытается применить первую комбинацию, если не получиться то вторую и т.д.
Естественно не забываем сделать sudo update-grub
Почитать о настройка GRUB2 можно здесь:
http://help.ubuntu.ru/wiki/grub
http://ubuntologia.ru/grub2-settings-file
