Este é o Ubuntu 12.04, 12.10 ou 13.04?
De qualquer forma, abra um terminal usando Ctrl - Alt - T e execute este comando:
sudo update-grub | tee ~/update-grub.txt
Você precisará digitar sua senha. Depois disso, tente reiniciar. Se ainda assim não funcionar, forneça o conteúdo do arquivo chamado update-grub.txt localizado em seu diretório pessoal.