'...converted our document to mac...'
Does this mean that YOUR document was created on a PC?
If so, then fonts are the last remaining big hiccup between the PC and Mac platforms. They are different, even if they have the same names.
It sounds to me like the printers were replacing your PC fonts with the closest equivlent Mac versions. I would be worried about that, as you will invariably get text reflow, which will change your layout. If you are producing these PM files on a PC, find a printer who can print directly from them rather than having to first convert them to a Mac format.