One last thing(I just thought of).
Is there any chance that you send them another file that you may have edited for printing purposes.
I do this myself.
What I tend to do is to always use sRGB mode for the entire
workflow(even still, after I acquired my aRGB monitor). It's just simpler with less risk for an issue somewhere.
But, what I have done(and will probably still do if I print anything else), is to also convert the
raw file to aRGB and edit that file to a point where I save it an another copy of that image just for the purpose of printing it.
Did you do something like that?
Did you tweak the file in any way prior to getting it to the printer? if you emailed it or uploaded it to their site, can you retrieve it to see if it has been edited in some way.