It could be your copy of GRUB is damaged. I have two suggestions:
- Use Boot Repair from an emergency disk to re-install GRUB.
- Use my rEFInd boot manager (the USB flash drive or CD-R version) to boot to your regular system. You can then either do a
sudo grub-install /dev/sda or install the rEFInd PPA or Debian package for a permanent solution.
Note that the second option will work only if Secure Boot really is disabled. It sounds like you're not 100% certain that it's disabled, and in fact, that is another possibility -- if an update installed an improperly-signed Shim, or if your firmware is finicky about its Secure Boot signatures, it could be that your system doesn't like an updated Shim. In this case, going back into the firmware and disabling Secure Boot is the proper solution, at least in the short term. I show several examples of how to disable Secure Boot on this page of mine, if you need some examples. (Unfortunately, the user interfaces for doing this are not standardized.)