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: