If the problem does lie with their software RIP not properly rasterizing the tranparency effects, you could always downgrade your PDF to Acrobat 4.0 (PDF version 1.3). Notice that the industry standard settings for the PDF/X setting default to Acrobat 4.
The “Press” setting you are using defaults to Acrobat 5 (1.4)
The difference is, when the PDF is created the transparency effects are flattened and therefore SHOULD be easier for you printer’s RIP to process. You can still select the “Press” preset, but just change the compatbility to Acrobat 4. When you do this a new option becomes available under the Advanced pane of the PDF Export Dialog box: Transparency Flattener. Choose the the High Resolution Setting.
Alex