First remove your old grub
sudo apt-get remove grub
Then Install the gfxboot-grub
sudo dpkg -i grub-gfxboot_0.97-5_i386.deb
then we’re going to move the message
sudo cp message.suse /boot/grub/
replace .suse with the .whatever you downloaded.
THE MESSAGE FILE MUST BE OWNED BY ROOT USER/GROUP WITH CORRECT PERMISSIONS
sudo chown root:root /boot/grub/message.susesudo chmod 644 /boot/grub/message.suse
replace .suse with the .whatever you downloaded.
Then edit your menu.lst
sudo cp /boot/grub/menu.lst /boot/grub/menu.lst_backupsudo gedit /boot/grub/menu.lst
and make it use gfxboot, write this as the very first line of the file and save it.
gfxmenu /boot/grub/message.suse
replace .suse with the .whatever you downloaded.
Then do :
sudo grub find /boot/grub/stage1
it’ll print out (hdx,y), so following that type:
root (hdx,y)setup (hdx)quit
if you have multiple (hdx,y) entries, work out which one is your
current OS partition and use that (note: grub counts from 0 onwards,
eg. hd0,0 is first harddrive, first partition, and it includes extended
partitions in it’s count).
NOW REBOOT. technically the above should have installed grub correctly,
if so then you can stop here. but for whatever reason for quite a few
people here it’s not, so on we go…
find out your hard drive names:
sudo fdisk -l
this helps with both the above and below. if you don’t know if
your OS’s partition is on hda, hdb, sda or anything else, then find out
using the above.
Install grub to MBR but CHANGE HDA to your OS’s drive, so if it’s on hdb use /dev/hdb:
sudo grub-install /dev/hda
DO NOT use any numbering in this,
using hda1 will install grub to the first partition not the mbr. if you
do this, follow this guide tellingly titled Oh crap, I just typed ‘grub-install /dev/hda1′.
you could use grub-install hd0 as with the grub setup command but this
is bios dependent and i dunno if you could mess it up by altering bios
settings inbetween things (and i don’t wanna find out either…).
and that should be it. restart and pray you didn’t mess up 
http://ubuntuforums.org/showthread.php?t=208855&highlight=gfxgrub&page=56