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?
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.