Empecemos, arranca desde el cd o desde donde tengas el Super Grub Disk y te aparecerá una pantalla como esta:
Selecciona la 1 opción, si no te funciona y te has cargado el grub al instalar el "maravilloso" windows prueba con la 3 opción. Te mostrará los SO que tienes instalados para que elijas con cual quieres arrancar.
Si no quieres utilizar el SGD puedes utilizar un Live CD siguiendo estas instrucciones y después sigue a partir de aquí.
Llegados a este punto ya habrás arrancado Ubuntu, ahora abre un terminal y vamos a recuperar el grub:
sudo grub-install --recheck /dev/sda(Cambia sda por tu disco duro, sda es el 1, sdb el 2 y así sucesivamente)
Y por último actualiza las entradas del GRUB:
sudo update-grub
Y ya tendrás el GRUB reparado.
Página de Super Grub Disk: http://www.supergrubdisk.org/