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.