Hay varias formas, de hacerlo, pero la que veo más sencilla es la siguiente: editar como root el archivo(si no existe, habrá que crearlo)
/usr/share/desktop-base/grub_background.sh
Y modificar (o crear)la linea:
WALLPAPER=/usr/share/images/desktop-base/debian-blueish-wallpaper-640x480.png
Poniendo en ella la imagen que queramos (yo soy un poco carca y me gusta el antiguo azul de Debian). Hay que tener en cuenta que según la imagen que pongamos habrá que modificar también el color de la fuente para verlo bien poniendo:
COLOR_NORMAL=black/black COLOR_HIGHLIGHT=white/black
El segundo color es el color de fondo, que si no se pone «black» nos tapa la imagen.
P.D.: Esto funciona en Debian 6 y en Ubuntu 10.04. En otras distribuciones o versiones es posible que no sirva, porque la implementación de Grub2 es diferente en cada caso.