Você precisa instalar o grub-installer.
Veja relatório de erros 776633 para um patch :
Index: grub-installer-1.60ubuntu3/grub-installer =================================================================== --- grub-installer-1.60ubuntu3.orig/grub-installer 2011-05-03 12:00:57.553509999 -0700 +++ grub-installer-1.60ubuntu3/grub-installer 2011-05-03 12:04:02.873000831 -0700 @@ -286,7 +286,7 @@ /dev/loop) disc_offered_devfs="$bootfs" ;; - /dev/[hsv]d[a-z]|/dev/xvd[a-z]|/dev/cciss/c[0-9]d[0-9]*|/dev/ida/c[0-9]d[0-9]*|/dev/rs/c[0-9]d[0-9]*|/dev/mmcblk[0-9]|/dev/ad[0-9]*|/dev/da[0-9]*) + /dev/[hsv]d[a-z]|/dev/[sv]d[a-z][a-z]|/dev/[sv]d[a-z][a-z][a-z]|/dev/xvd[a-z]|/dev/cciss/c[0-9]d[0-9]*|/dev/ida/c[0-9]d[0-9]*|/dev/rs/c[0-9]d[0-9]*|/dev/mmcblk[0-9]|/dev/ad[0-9]*|/dev/da[0-9]*) disc_offered_devfs="$prefix" ;; *)
O instalador do grub provavelmente não está no seu sistema (já que depois de instalado, não é necessário que ele permaneça;)). Este é o pacote que interessa: link , então você provavelmente o encontrará no meio de instalação ...
Aqui está um rápido como remasterizar seu próprio CD: Como posso remasterizar o Ubuntu facilmente?