5100cn fails to print

I'm using a 5100cn laser printer networked in an office environment with computer running Windows XP SP3 (and a couple Macs). We are having a problem where sometimes (seems random!) a computer will send a print job to the print and the printer will warm up as if it is about to print, but then will not actually print the document. The XP machine will report that the job was successfully printed, but the printer will not actually print (only warm up as if it were going to print).

Turning the printer off and back on again does not fix the problem. It is not a problem with any specific machine on the network, though it seems to happen more often with some of the XP clients than others (and never with the Macs). Often, just printing a different document than the one that is currently open will make it print ok again, but it's not a document corruption issue because it can happen with any given document (in MS excel, Word, Outlook, etc).

Any suggestions?