Are you using the latest drivers off their web site, or the drivers on the CD in the box? Are you using the postscript or PCL driver? Can you try whichever one you are not using?

"Random" errors are always a pain to track down. Since this hasn't been reported as a problem at other sites, I'm more inclined to point a finger at the printer and/or its driver.