Bueno, aca te dejo una guia paso a paso para poder hacerlo.
Lo primero que tenes que hacer es bajarte este archivo:

o simplemente tipear esto en la consola:

wget http://quasarfreak.googlepages.com/grub-gfxboot_0.97-5_i386.deb

Ahora, vamos a desinstalar tu antiguo grub de la siguiente manera:

En la consola

sudo apt-get remove grub

Y procedemos a instalar el nuevo grub:

En la consola

sudo dpkg -i grub-gfxboot_0.97-5_i386.deb

Atencion aca, en la consola vamos a usar el comando fdisk para ver la tabla de particiones para saber donde vamos a instalar el nuevo grub, tipeamos:

En la consola

sudo fdisk -l

y vamos a ver algo como esto:


Bueno yo en la captura remarque /dev/sda/ que en mi caso ese es el disco donde vamos a instalar el grub, en general si tenes un disco sata va a ser en /dev/sda/ mientras que en los ide va a ser /dev/hda, pero no se confien de esto, verifiquen mediante fdisk donde deben instalar su grub.
Ahora dependiendo del disco que tengamos tipeamos:

En la consola

sudo grub-install /dev/sda #si tu disco es sata#

sudo grub-install /dev/hda #si tu disco es ide#

Bueno aca les dejo 2 temas para gfx-grub, en www.gnome-look.org pueden encontrar muchos mas.
Este es el del primer screenshot http://www.gnome-look.org/content/download.php?content=70107&id=1&tan=32517008
Este es el del segundo http://www.gnome-look.org/content/download.php?content=58248&id=1&tan=38632865

Cuando hayamos elegido un tema lo descargamos y lo guardamos en /home/Usuario/ (donde Usuario es tu nombre de usuario) y vamos a tener un archivo tar.gz o bien un zip dentro del archivo comprido vamos a tener un archivo del tipo message.XXXXXX donde XXXXXX es el nombre del tema, lo descomprimimos.
Y en la consola tipeamos:

En la consola:

sudo cp message.XXXXXX /boot/grub/

Una vez copiado el tema debemos editar el grub de la siguiente manera:

En la consola

sudo gedit /boot/grub/menu.lst

y en la primera linea vamos a poner:

gfxmenu /boot/grub/message.XXXXXX

Guardamos y Listo

Cuando reinicien la maquina les va a quedar un menu de booteo estilo SUSE.

Espero se entienda bien el procedimiento, trate de hacerlo de manera que cualquier usuario nuevo de ubuntu pueda hacerlo.

Esta guia esta redactada por mi, pero yo lo hice en base a un tuto hecho por Maverick y publicado en http://www.elblogdemaverick.com.

Edit:

Para los que tengan AMD 64b el paquete es el siguiente:

http://kanotix.com/debian/pool/main/g/grub-gfxboot/grub-gfxboot_0.97-11_amd64.deb

o simplemente en consola:

wget http://kanotix.com/debian/pool/main/g/grub-gfxboot/grub-gfxboot_0.97-11_amd64.deb

Y depues lo instalamos asi:

en la consola

sudo dpkg -i grub-gfxboot_0.97-11_amd64.deb

el resto del procedimiento es el mismo.