Windows Update Failing for No Reason?

I’ve built a couple of new Lenovo T420s laptops at work the last couple of days.  On both machines Windows Update refused to check for updates:

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

Being that I had repeatedly restarted the machine as I built it and added different software I was convinced that yet another reboot would not help the matter.  I rebooted anyway.  It did not help the matter.  (“Windows, you lied to me!”)

I checked the service and found that it was running as expected.  I restarted it just for shits and giggles.  It restarted smoothly and rapidly.  This also did not help the matter.

Finally I opened Windows Update and clicked on “Change settings”.  I told Windows Update to “Never check for updates (not recommended)”.  After re-opening Windows Update I set it back to my usual setting, and like magic it checked for updates.

Confused little application…

Anyway, hope that helps you.