Is the gradient created from two colors or does it include transparency (i.e., does it fade from a color to transparency)?
There are several page description languages (PDL) that that tell the printer what a document looks like. It is likely that the problem is with the printer drivers and the PDL that it used.
In my opinion, the document you provided is not corrupt. It is the client’s printer and driver that are the problem. I would offer the following solutions:
1. Ask them what model printer is giving them issues. Most modern printers can handle transparency. You can recommend that they ensure the most up-to-date driver or RIP available for their printer. In addition, they may want to see if there are alternative drivers. In the case of Windows users, they can check for Enhanced PCL drivers.
2. Consider exporting without transparency. Exporting as PDF/X-1a:2001 should do the trick. Alternatively, you can set you desired export options and then set “Compatibility” to “Acrobat 4 (PDF 1,3)”. See if they still have issues.