Eu tive exatamente o mesmo problema há algumas semanas com o 12.04 (e também com o não funcionamento 13.04 install). Eu entendi que eu instalei o Ubuntu em uma partição Windows, que foi a razão pela qual o Ubuntu não o reconheceu.
Eu instalei manualmente na partição e instalei o GRUB em um disco rígido externo. O GRUB foi de fato excluído no meu disco rígido. Depois, reiniciei o disco rígido e consegui inicializar em minha nova instalação, onde eu podia configurar o GRUB corretamente. Isso é um pouco confuso e eu não posso garantir que vai funcionar, mas fez por mim.
Existem outras maneiras de instalar o GRUB a posteriori, por exemplo, usando um liveCD e Boot-repair