Sua situação é resolvida reinstalando o grub. Para isso, você precisa inicializar a partir do seu live CD do Ubuntu e abrir o terminal permitirá que você instale novamente o grub.
Aqui é alguma documentação.
Eu instalei o windows 8 no meu computador e estraguei minha partição do Ubuntu. Agora não consigo fazer meu Grub subir. Aqui está o truque, eu instalei o Ubuntu dentro do Windows e até tentei a correção que foi dada nos fóruns aqui, Partição Dedicada GRUB2 e Windows 8 .
Isso não funcionou. Uma reinstalação completa do Ubuntu seria a única correção? Estou totalmente perdido e já estou ficando cansado do Windows 8: p.
Não se preocupe! Eu tive esse mesmo problema antes! Sua instalação está bem!
Simplesmente inicialize em seu computador usando o Live CD (e também arquivos de backup, se desejar fazê-lo agora). Em seguida, reinstale ou atualize seu GRUB.
Não entre em pânico. Quando você instala o Windows, o Windows presume que seja o único SO na máquina - ou pelo menos não conta para o Linux. Então, ele substitui o GRUB por seu próprio gerenciador de inicialização.
O que você precisa fazer é substituir o bootloader do Windows pelo GRUB. Basta chroot na sua instalação e execute o update-grub.
Veja como: Como posso reparar o grub? (Como obter o Ubuntu de volta depois de instalar o Windows?)
Veja isso também Pergunta semelhante em superuser.com