Sounds like you already found the solution, but this is what worked for me and a couple of others running Windows 7 Pro:
Hi
For Windows 7 (Pro) with error message:
"Windows Update cannot currently check for updates because the service is not runnning. You may need to restart your computer."
Sounds like your error is the same type I had. I guess there is an expired microsoft certificate that is the problem.
I am by no means a computer expert, but did find a quick fix that worked on my computer, and also on a friend's computer.
(I found the info on a blog) This is what I did:
1-Go to the windows start button
2-Click on Control Panel (on the right, in the blue shaded area)
3-Click System and Security
4-On Windows Update, click turn automatic updating on or off
5-Under Important Updates, next to the Green Shield, click the drop down menue
6-From that drop down list, click never check for updates, even tho it says not recommended
7-Click okay
To then get updates
Repete steps 1, 2 and 3
Under Windows Update, click check for updates
My computer then successfully checked for the updates, and I installed them.
Then, you can go back to the drop down menue in step 5 and change it back to install updates automatically, or to one of ther other options
Hope this helps