I have exactly the same problem with Windows 7 and Samsung SCX 4100.
At first my printer worked without askind to install anything, though scanner did not, so I downloaded newest scanning and printing drives for my device. The scaner works perfectly, but the printer doesn't.
When I try to add a new printer, I got the same message about spooler service.
I go to Windows Task Manager, and start the service manually - but after 3 seconds from the status 'started' it automatically changes into 'stopped'.
What should I do now?