Abrid un terminal(Aplicaciones>Accesorios>Terminal) y escribid:
sudo apt-get remove grub2 grub-pc
Descargar e instalar grub-gfxboot, para 32bits o para 64bits
En el terminal escrivimos:
sudo grub-install /dev/[hda1 o hdba2 lo q sea(lo mismo os puede ayudar escrivir sudo fdisk -l
e n el terminal para saber cual es la particion correcta, normalmente sera la primera)]sudo update-grub
sudo gedit /boot/grub/menu.lst
Y añadimos arriba del todo:
gfxmenu /boot/grub/message.ubugrey
Os recomiendo bajar un tema como este, si poneis este tema tedriamos que cambiar gfxmenu /boot/grub/message.ubugrey por gfxmenu /boot/grub/message.debianorange