Este é o problema.
Faça isso:
em / etc / default / grub encontre a linha
GRUB_GFXMODE=auto
e descomente / mude para
GRUB_GFXMODE=1920x1080
GRUB_GFXPAYLOAD_LINUX=keep
Depois, em /etc/grub.d/00_header encontre a linha que começa com
if [ "x${GRUB_GFXMODE}" = "x" ] ...
e mude para
if [ "x${GRUB_GFXMODE}" = "x" ] ; then GRUB_GFXMODE=1920x1080 ; fi
então, abaixo, encontre o bloco abaixo
set gfxmode=${GRUB_GFXMODE}
e mude para
set gfxmode=${GRUB_GFXMODE}
set gfxpayload=keep
load_video
insmod gfxterm
depois, execute
sudo update-grub
Reinicie e tudo deve estar OK.
Testado a partir do Ubuntu 13.04 e Mint 15 com uma Nvidia GeForce 9600 GT.