I've seen this bizarrely happen on a newly partitioned and custom installed Linux install, particularly if you did not properly unmount before rebooting.
You can find reports of it happening on various
You need to boot into Live/Rescue mode, chroot into your OS properly and then do a grub-install on each drive that needs to be booted from.
The solution to avoid the problem is to make sure that /boot and / are properly unmounted and I've never seen that error. I have confirmed that it can even happen on a successful grub-install if you don't unmount properly.