Você não precisa reinstalar o Ubuntu, apenas reinstalar o Grub. Você pode inicializar a partir de um LiveCD do Ubuntu e tentar reinstalá-lo:
Abra a versão ao vivo. Abra o terminal e execute sudo fdisk -l para ver onde o Linux está instalado.
Execute sudo mount /dev/sdaX /mnt onde X é o número em que você encontrou a palavra do Linux.
Execute sudo grub-install --root-directory=/mnt /dev/sda para instalar o grub.
Execute sudo update-grub para atualizar o grub.
Reinicie.
Mais informações sobre a reinstalação do grub: