Can't run Windows Update

Hi. Yesterday, I factory reset my dad's computer and now I can't run Windows Update. When I attempt to, I get the message, "Windows Update cannot currently check for updates, because the service is not running. You may need to restart your computer." I've restarted it THREE TIMES!!!! Can anyone help? Thanks! Computer is a Gateway FX6831.
 
Solution
Download and install this update:
KB3112343
(windows update service must be stopped before doing that)

This fixes windows update problem with freshly installed windows 7.