Cuando me pasó algo parecido en WinXP, no pude restaurar el MBR con "fdisk /mbr" (no me pregunten la razón, mejor pregúntenle a nuestro amado Bill Gates
). Tuve que entrar en modo rescate con el CD de WinXP y ejecutar los comandos "fixboot" y "fixmbr". Y después entrar en modo rescate con el CD de Linux y ejecutar "grub-install /dev/hda".
Espero que esto te ayude.