I've run into an issue with my printer denying printing, one of my designs is a parody of Hotline Bling and contains the familiar text in Helvetica Neue in the background.
The reasoning is because of copyright issues but from my research about copyright rules, you cannot copyright the use of a typeface.
You can trademark a logo. And a logo can be made from a typeface. It's less protectable than something custom, but protectable none-the-less.
But parody is a perfectly acceptable.
I'd find a new printer.
I know this doesn't fully answer it, but I found an interesting article that may help with your project:
The Law on Fonts and Typefaces
It seems like you should be able to incorporate it into your design though. I will update this if I can find specific references from my law buddies.
There are many areas to look at to reason the printer's decision.
The font in question is a commercial font, produced by Linotype. In order to use the font, you would have needed to purchase it (they have different licenses available, depending on usage). This means that it is protected by copyright law.
Now to the tricky part, and this is what your printer is being cautious about. If you provided your artwork, with the fonts, it means that they would not be able to use it to process the job as they need to install the fonts on their system (which costs them money).
You cannot provide them with the fonts, as this would be illegal under the licensing agreement (given that you purchased the license).
A workaround is to always convert your text to outlines before submitting to the printer. It is perfectly legal to produce and provide a work using a commercial font, as long as you do not provide it with embedded commercial fonts that would require the printer to purchase them.
To think about it from the perspective of the printer; if they had to purchase the fonts for every job that they are receiving, they'll be spending countless time and money doing that – unfeasible.
