Hoy me puse a trastear un poco con Ubuntu y Windows, en uno de esas -zas- que me vuelo el grub y ya no podía acceder a Ubuntu. Después de varias búsquedas y encontrar soluciones como el WinGRUB (para recuperar el GRUB desde Windows).

Puedo asegurar que la opción que me resulto mas efectiva es corriendo Ubuntu desde LiveCD (a traves de USB tambien se puede) y luego restaurar el GRUB con algunos comandos en la consola.

Detallo lo pasos que seguí:

1- Arrancar con LiveCD o USB

2-  Abrimos la consola y tecleamos:
sudo fdisk -l (muestra particiones)

2- Montar la partición donde esta instalado Ubuntu (sustituir X por el numero correspondiente a la partición, por ejemplo si es sda1, 1 seria el numero a cambiar por X):
sudo mount /dev/sdax /mnt (en /mnt debes montar la partición donde está tu linux)

Por ejemplo:

3- Procedemos a montar el resto de dispositivos:
sudo mount --bind /dev /mnt/dev

4- Acceso de root a todo lo montado
sudo chroot /mnt

5- Este es penúltimo paso y aquí no hay que cambiar nada, dejas sda tal como esta sin agregar nada mas:
grub-install --recheck /dev/sda

6- Reinicia normalmente, sin LiveCD.

7- Ya en Ubuntu y viendo que todo esta correcto, abrimos una consola y actualizamos el Grub:
sudo update-grub2 o sudo apt-get update -grub2

Si no funcionare entonces instalamos:
sudo aptitude install grub

Imagen vía | MysticTempest