I've encountered this after upgrading some Debian/Ubuntu/Mint based systems for no explicable reason, although there are some bug trackers on Ubuntu that document this: https://bugs.launchpad.net/ubuntu/+source/grub2/+bug/1889509
The short end of the solution is that you need to properly reinstall grub.
1.) Boot from a LiveCD
2.) Mount your root / filesystem and don't forget to mount the boot partition in the root's /boot (if you have a separate partition).
4.) Reinstall grub
#(where X is one of your boot drives).
After that you should be good.