Maybe the font isn't embedded. On systems with the font, then, you will see it as intended, otherwise it will substitute.
But yet on original on same computer font is fine, only when you save in reduced format this happens?
Exactly what options were used to reduce, in exactly what version of which software? One way to reduce size is to remove fonts from the file, so this may be exactly what is expected. Depends.