Have a look at some of your print settings. When you select File > Print..., go to the Options tab. In the pictures section, make sure 'Output' is set to Normal. To get rid of that warning message, change the Data drop down list to Binary. Having said that, ASCII is probably more compatible, so I would be suprised if that solved your problem. Still, worth a shot I suppose!
BTW, when you go to Utilities > Usage... and click Pictures, do all your images show up as OK? Also, do you have other images in your Quark document that are causing problems? Are there other EPS files that print normally? Is the gradient part of the EPS file, or is it generated by Quark in a picture box with an imported EPS file?
Sorry for all the questions!