Hoy en la tarde me dio por reinstalar Windows en su partición, y claro, ésto tiene como consecuencia que en adelante GRUB desaparece, con lo que no puedo iniciar Ubuntu...
Solución, arrancar con el CD de instalación de Ubuntu, y en la línea de comandos ejecutar:
$ sudo sudo mkdir /dev/sda2
$ sudo mount /dev/sda2 /mnt/sda2 -t ext3
$ sudo grub-install --root-directory=/mnt/sda2 /dev/sda
La primera línea monta el sistema de archivos de mi partición de Ubuntu y la segunda reinstala GRUB.