"Operation could not be completed. The print spooler service is not running."

I had same problem, lost the print spooler, printer access and could not restore either one.    The problem was caused by the malware virus Win32/FakeRean.   Once this virus was removed (read COMPLETELY REMOVED), the print spooler and all the printer connections restored automatically.

Other symptoms: A bogus computer scan, fake firewall violations and a security protection sales pitch appeared after each reboot.  Microsoft Security Essentials claimed to remove this bogus scan, albiet, only partially.  The system ran okay, but the print spooler kept turning off.  The malware was still there.  If you just hibernate your PC, you likely won't see the bogus computer scan and sales pitch.  This symptom only appeared during reboots.

Solution:  I ran Microsoft's Safety Scanner program.  It found the infected files and removed the root source of the Win32/FakeRean.   The print spooler and printer operation returned to normal.   The following links may be of use.

Microsoft's Article ID: 129972 - "Computer viruses: description, prevention, and recovery".  This is a GREAT tutorial on viruses and remedies.  It includes a link to the Safety Scanner program along with other tools.
http://support.microsoft.com/kb/129972

The Safety Scanner is directly downloadable at…
http://www.microsoft.com/security/scanner/en-us/default.aspx