You get: “Windows Update cannot currently check for updates, because the service is not running. You may need to restart your computer.” on Windows 7 when checking for updates.
In my case, this happened on two computers that both were infected with the ZeroAccess trojan. The reason this message appears is that the malware deleted the registry keys for Background Intelligent Transfer Service (BITS) and Windows Update (wuauserv).
I searched and searched today, but came up empty trying to find a utility or easy fix. Thankfully, I previously figured this out and here is what to do: (this is an advanced fix and I highly recommend leaving it for professionals; I cannot support you if this causes problems)
1. Run SERVICES.MSC after hitting WINDOWS-R and look for Windows Update and Background Intelligent Transfer Service in the list of services. If they are missing, keep going.
2. Visit Smartest Computing’s cache of registry keys. Click Download at the top and save the SEVEN.ZIP (or adapt this if your OS is different) and pull out the bits.reg and wuauserv.reg, double-click each one and restart the computer.
3. Leave a comment if this worked or not. There are times when the files have been changes or removed that this wouldn’t work.
[UPDATE 4/2013] If this doesn’t work for you, Tweaking.com has an All-in-One Windows repair tools that has had success with some: http://www.tweaking.com/content/page/windows_repair_all_in_one.html I’m interested in feedback on that tool.