Google for issues with the spooler.
Also check if you can print without issues from other apps on the problem machines.