Eu tive um problema semelhante depois de instalar o Fedora 17. O Ubuntu não iria buscá-lo. Depois de não encontrar respostas na net, eu me perguntei se era porque o grub não podia 'ver' a instalação do Fedora. Então montei a partição Fedora / no Ubuntu e rodei o update-grub e ele encontrou a instalação do Fedora e a adicionou ao menu de inicialização. Eu uso a mesma técnica com o Archlinux