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
update-grub
grub-install /dev/sdx
#(where X is one of your boot drives).
After that you should be good.
grub_calloc, grub, fixi, ve, encountered, upgrading, debian, ubuntu, mint, explicable, trackers, https, launchpad, reinstall, livecd, mount, filesystem, partition, chroot, install, update, dev, sdx,