I had the problem described, and followed the top two procedures, explained here: How to restore a system after accidentally removing all kernels?
I have a separate boot partition, and I used the above described procedure to mount it to /mnt/boot
I was able to complete everything successfully, but GRUB boot menu still does not contain a Linux distro. In other words, when I boot, I am left at GRUB boot menu and no option to boot into Ubuntu.