I had this problem recently and it seems (touch wood) the problem lay the driver one of the network printers installed when you added the printer.
What i did (as we only have a few clients using this) was just to delete the device, get the late drivers from manufacturer and manually specify the printer using tcp/ip and choosing the driver myself (also deleted all the "extra printers" like
fax and document writer.
We also migrated from 2007 to 2010 on one of the affected machines and left 2007 on the other to see if we had to do a mass migration.
A little bit of a swine of a solution some might say but seems to have worked okay!
Microsoft is conducting an online survey to understand your opinion of the Technet Web site. If you choose to participate, the online survey will be presented to you when you leave the Technet Web site.