Windows cannot check for updates because the service is not running. You may need to restart your computer.

We recently had a Toshiba Satellite laptop in the shop that we needed to replace a hard drive in due to failure.  Things went well until we tried to update Windows.  No matter what we did, we were faced with the message "Windows cannot check for updates because the service is not running.  You may need to restart your computer."  Another symptom was that Windows Defender could not update either (mostly due to the fact that it uses Windows Update to receive them).

So, after a bit of research, it appeared that our particular case was possibly due to the need for an update to the "Intel Rapid Storage Technology Driver".  This Toshiba did have an Intel chipset and Intel graphics, so it sounded reasonable.

Due to the fact we replaced the original drive with a Western Digital drive, the particular driver update we needed was nowhere to be found on Toshiba's website.  It was proving actually rather difficult to find, but I kept looking and ran across this nice little blog post which referred to my exact problem. 

The blog post mentioned an HP page which documented the error (among others) due to this particular issue and had an HP download located there.  The mentioned HP link is here:  http://h10025.www1.hp.com/ewfrf/wc/document?docname=c02219204&lc=en&cc=uk&destPage=document&dlc=en&product=

Now, even though I was on a Toshiba laptop, the HP link just had an HP packaged file that extracted to run and Intel installer, so it worked regardless.  I extracted the HP file and ran the Intel installer, rebooted the computer and holy smokes, Batman!  Windows Update works!  

Thanks G-Fav for a link to the HP download!