I design forms and fliers for a school district. Multiple times I have witnessed my colleagues print the PDFs that have been generated from me in InDesign CS6, and the font is replaced and incorrect. The PDF looks correct on the screen, but not correct when printed.
I would have thought perhaps this is a problem with their computer or their printer, but there are too many who are having this problem, and so I'm thinking it's more likely that it's a problem with my export. I am exporting using the standard "High Quality Print" setting.
I have checked the PDF properties after export, and it says the fonts are embedded, or at least a subset is embedded. This is happening with multiple standard fonts (Calibri, Myriad Pro), so it's not a font file issue.
Can you post a few screenshots and/or scans?
How are these PDFs printed? Anything but Reader/Acrobat is a crapshoot. Apple Preview is complete junk.