Maldita sea lo voy a poner aquí de una vez por todas…

1. Arrancar con un un live cd
2. Entrar aquí:
$ sudo grub
3. Buscar esto:
> find /boot/grub/stage1
4. Escribir esto:
> root (hdX,Y)
( hdX,Y) no es inventado obviamente, es el resultado del paso 3, en mi caso es (hd0,6)

5. Sigue esto:
> setup (hd0)
6. Y
> quit

Con eso debe quedar listo…

Ah si, lo encontré aquí.