Comment 31 for bug 1848797

I was able to fix it by booting my cloud provider's rescue image and do the following:

mount /dev/sdXY /mnt
mount --bind /dev /mnt/dev
mount --bind /dev/pts /mnt/dev/pts
mount --bind /proc /mnt/proc
mount --bind /sys /mnt/sys
chroot /mnt
grub-install /dev/sdX
update-grub
exit
reboot

(https://howtoubuntu.org/how-to-repair-restore-reinstall-grub-2-with-a-ubuntu-live-cd)