What's the physical printing topography? Are the printers directly connected, or is there a central print server that all the clients point to or does each client print directly to a network printer with no print server as an intermediary?

If it's the second setup (client -> printserver -> network printer(s)) then have you tried reinstalling an updated driver on the printserver? If it's not, can you set up a machine as a print server and try redirecting the problem machines through it as a trouble shooting step?

If they are printing over the network (machine -> networked printer(s)) are you using TCP/IP ports? Try deleting and recreating the TCP/IP ports (or HP Jetdirect or whatever) and re-creating them. I've solved quite a few print problems with this trick, and I have no idea why it should work, but it very often does. This trick often works on the printservers too.

-Zeke