Hopefully the following helps. I had to home-grow my own solution because no one on the Net seemed to know how to fix it. Hopefully it helps someone else out there.
So you obviously know how to open up services. Good stuff. For everyone else out there, go to Start -> (All) Programs -> Administrative Tools -> Services. That's for Windows XP. Let me know if you have another version of Windows.
At the bottom of the window, you'll see two tabs - "Extended" and "Standard". Ensure that the "Extended" tab is selected. In the list of services, locate "Print Spooler" and click on it. Now, look just to the left of the list of services and you might see some blue text that says "Start Service". Try clicking this first. If it does start, you're done! Try printing something.
If the print spooler doesn't start, or you don't have the choice to "Start Service", you'll have to go a bit deeper. Back to the list, right click on "Print Spooler" and select "Properties". Select the tab that says "Dependencies". There will be two lists - the top one is system components on which the Print Spooler depends - it's 'dependencies', and the bottom is system components which depend on the Print Spooler. We're concerned with the top list of services.
The idea in summary is to ensure that any services that the "Print Spooler" depends on are started. Know how to do that? Then go nuts. Otherwise, follow along.
If there are any '+' signs next to a service, select it. You'll want to see all the levels of the "Print Spooler" dependencies - second-level dependencies are those that appeared under another service when you clicked on the '+' sign. Go back to the main list of services and locate those second-level dependencies in the list one by one. (You shouldn't have to close the "Print Spooler" properties window to go back to the main list.) When you've find a dependency in the main list, click on it. Do you see that blue "Start Service" text to the left? If so, click it. Hopefully it'll start. If you get an error, let me know.
You'll want to find and start those second level dependencies first. Then find and start the first level dependencies. Once all this is done, close the "Print Spooler" properties and locate "Print Spooler" in the main list again. Try to start it. Hopefully it'll start.
Didn't work? I've also heard people complain of getting the error you got when they had viruses - a Trojan in particular, so you might want to do a scan of your computer. There's lots of good, free anti-virus software out there - I personally use avast!.
I hope this can help.