It sounds like the fonts are limited by a licnese or they are not in a compatible format for the PDF usage.
Back to the topic of Font-Embeds: There is another way some Production Specialists use. And that is to Print the PDF files to another PDF, and having the settings to include to Embed Fonts.
Does this work as well?
Some fonts are licensed with a restriction, that is machine enforceable, not to be embedded or transferred with an electronic document. So you first need to see if this applies.
You could try creating an image of the magazine pages.
Reprinting a PDF through the Adobe PDF printer is known as 'refrying' and like frying a meal a second time, the results are seldom as good as the original.
Have a look at the Pre-Flight process.