A mi me ha pasado algo parecido hace poco. Actualicé mi sobremesa, tenía una instalación de windows y una de ubuntu 12.04, pues cuando fui a instalar Ubuntu 13.04 con el nuevo equipo hacía la instalación completa pero después no arrancaba, me entraba al grub rescue> o lo más que conseguí fue llegar a grub>, pero todas las particiones que detectaba eran de msdos y nunca conseguí cargar el kernel, así que indignado, vacié un disco duro y lo formateé completamente con el sistema. Fue la única forma de conseguirlo.
Sí te diré que en mis múltiples reinicios y accesos a la UEFI descubrí que hay un apartado donde se configura el sistema operativo "seguro" y por defecto viene windows, yo lo puse otros OS, o algo así no lo recuerdo. Te recomiendo que le des una vuelta a todos los menús porque está por ahí.