Tiez som mal podobne problemy (s trochu starsim ubuntu, tusim 7.10) a pomohla uz J. R.-om zmienovana uprava grub boot menu.