Estes são os passos que eu sugeriria.
- Inicialize a partir do CD ao vivo.
- Localize a partição anterior do Ubuntu e monte .
- chroot na partição montada.
- Execute o comando grub-install .
Os comandos exatos podem variar dependendo das suas partições e estrutura de diretórios.