No se había eliminado bien y había que restaurar el sector de arranque. Para ello:
1.- Arrancas el LiveCD de ubuntu (En mi caso 16.4) y vas a la consola.
2.- Escribes:
- sudo apt-get install lilo
- sudo lilo -M /dev/sda mbr
Al instalar lilo igual dice que al ser la primera vez tienes que ejecutar comandos iniciales de configuración blabla, ni caso funciona bien.