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 mo........