I am also having the same issue with a number of Windows 7 machines on our domain. We have a few Windows 7 machines in different areas of the building, with different models of printer on each machine. There is nothing in the Windows event logs. A simple restart of the print spooler service fixes the issue.
Windows XP machines have been happily printing to these printers for years.
Has anyone else come across this?