The symptoms sound like you have a PostScript file being distilled for which the fonts were embedded in the PostScript but are not actually being used by the Distiller. One situation that could cause this is an option, on by default, for the Adobe PDF PostScript printer driver instance.
Go to the Printer Control Panel and right click on the Adobe PDF printer and click Properties. Go to the Advanced tab and click on Preferences. Click on Printing Defaults and select the Adobe PDF Settings tab.

In that dialog, make sure to deselect the Rely on system fonts only. Do not use document fonts option. (See below, pointed to by arrow!) Press OK all the way back to the Printer Control Panel. Restart the application from which you were trying to create PDF via Adobe PDF and see if that resolves the problem.
- Dov