It's strange that it prints some of the time, but not others. When you create an EPS and flatten it and place it again, it prints ok. When you get to this stage, it is essentially one large raster graphic, so it is much easier to interpret than the original document, which may have many complex elements.
To troubleshoot this, you might have to try a few techniques. To start with, instead of bringing the EPS into Photoshop, just place it as is. I would presume that the same problem will occur, but let us know if it doesn't.
You don't mention if you're using Quark 6 as well as your client. If you are, try back-saving it to 5 (on a backup document) and printing from that.
At this stage, it might be worth looking at the elements within the document. The quickest way to do this is to delete half the elements and see if the problem persists. If it doesn't, it may be something (image, font...) that you've deleted. Narrow it down by repeatedly removing half the remaining elements until the document works, then replacing items until the problem occurs again. You can also replace the fonts with something simple as a test.
All this is just guesswork, though. If it works on someone elses computer, it may just be a problem with your printer drivers. It's worth trying this, and upgrading your drivers if possible. Exporting a PDF and printing from that is another possibility.
