puff, justo ayer tuve un problemilla parecido. Tengo W8 y Ubuntu instalado, y al instalar una actualización de W8 solo me arrancaba con el grub rescue. Lo que hice fue lo siguiente...
1) ls para buscar las distintas particiones
2) Después, voy haciendo un ls a cada una de las particiones hasta encontrar la de linux (en mi caso "ls (hdX,gptY)/"
3) Una vez que se la partición, hago...
set root=(hdX,gptY)
set prefix=(hdX,gptY)/boot/grub
insmod normal
normal
4) Una vez dentro de Ubuntu, reinstalas el grub...
sudo update-grub
sudo grub-install /dev/sda (el sda en mi caso)
Espero que te sirva!