Boot Repair não funcionou comigo. Depois de muita pesquisa e tentativa, finalmente consegui recuperar o acesso ao meu Ubuntu com o seguinte conjunto de comandos:
sudo mount /dev/sdb8 /mnt
sudo mount --bind /dev /mnt/dev/
sudo mount --bind /dev/pts /mnt/dev/pts
sudo mount --bind /proc /mnt/proc
sudo mount --bind /sys /mnt/sys
sudo chroot /mnt
grub-install /dev/sdb
grub-install --recheck /dev/sdb
update-grub
exit
sudo umount /mnt/sys
sudo umount /mnt/proc
sudo umount /mnt/dev/pts
(Todos os comandos foram executados no LiveUSB)