I haven't seen this but here are some things to look at
Where is the pdf located...on the server, or the pc itself?
Try copying the pdf to the pc itself then open and try to print. If this works then look at the network such as privilages, etc.
Are you printing from Reader on the computers or the full verison of Acrobat?
Has it ever worked?
Try reinstalling the printer driver. Could be if it has worked before that the driver has corrupted.
Thanks
Iknonpro