Know this is a dumb question, but are you embedding the fonts? Or, maybe it's a font that can't be embedded due to legal restrictions?
In your Acrobat preferences, what do you see if you turn off "Use Local Fonts" under Page Display > Rendering?
What happens if you outline the fonts and then "Save As" a PDF?
It may be helpful to provide a sample .ai file, so one can take a look at it.
Just in case you're free to do that.
Never a dumb question if it it had pointed us in the right direction. Yes the fonts are all embedded (legally). We tried the Acrobat Preferences but the don't make any difference. If we outline the fonts in Illustrator the problem still happens when we do a save as so it doesn't seem to be a font issue.