Я бы для начала проверил, какой раздел является загрузочным (имеет метку bootable).
Еще один вариант, который может помочь.
Загрузиться с LiveCD, смонтировать корневой раздел, например в /mnt/sda. Подмонтировать /boot, если он выделен в отдельный раздел
Затем:
mount -o bind /dev /mnt/sda/dev
mount -o bind /proc /mnt/sda/proc
chroot /mnt/sda
И затем grub-install