Vamos a suponer que el disco es el sda y la particion de linux a rescatar es la sda3.
Una vez despues de haber booteado con el cd de rescate...
monto la particion en mnt...
# mount /dev/sda3 /mnt
preparo la particion...
# mount -o bind /dev /mnt/dev
# mount -o bind /proc /mnt/proc
y hago el change root...
# chroot /mnt
ya dentro del nuevo raiz...
edito el archivo de configuracion del grub..
# vi /boot/grub/menu.lst
NOTA: Para actualizar el archivo de forma automatica el comando amigo "update-grub" hace un buen trabajo. Basicamente lo que hace es buscar los kernel disponibles en el directorio "/boot" y crea una entrada por cada uno.
despues de haber cambiado lo que necesitaba...
lo instalo en el Master Boot Record
# grub-install /dev/sda
Con esto al menos deberia bootear desde esa particion.