Just noticed a very similar problem here at the office with one of the machines. Try right-clicking the printer and selecting properties. I get a message that the print spooler service is not running. Still working on it, because it looks as if it is.
I'll post back if I sort anything tonight.