проверить: + поменять еще и на шелл и проверить.

У меня на ~8-10 секунд ускорило добавление в /boot/grub/menu.lst в параметр к ядру concurrency=startpar, т.е. в результате строка должна выглядеть примерно так: 

/boot/vmlinuz-2.6.27-custom root=/dev/sda2 ro quiet concurrency=startpar