It's complete nonsense for them to say they can't print PDFs with OpenType fonts in them, if they can print PDFs with Type 1 fonts in them. Type 1 and OpenType fonts are stored the exact same way in PDF, and you literally can't tell which kind it is, except by the name.
Now, there are ways of making PDFs that may give problems to some PostScript "clone" RIPs, and other issues like that. But they are largely independent of font format going into the PDF.
If you present them with this information, and they still won't budge, I suggest you change printers.
Regards,
T
Thomas Phinney
Program Manager
Fonts & Core Technologies
Adobe Systems