Você não diz qual versão de grub
ou Ubuntu, mas se for aplicável, sugiro adicionar um pouco de rootdelay
à linha do kernel em /boot/grub/menu.lst
e ver se isso ajuda.
kernel vmlinuz ... rootdelay=90
Você pode tentar um valor menor pelo número de segundos.