Solução: Ainda não sei se funciona.
1. Bootar com live-cd do Ubuntu.
2. Montar a partição do Linux como root (montado em "/media").
3. Executar os comandos:
mount -o bind /proc/ /media/proc
mount -o bind /dev/ /media/dev
chroot /media/
Após fazer isso, os comandos do grub podem ser executados, pois o raiz do live-cd fica sendo o raiz da partição montada.
4. Executar os comandos do grub:
update-grub
grub-install /dev/sda