Its probably because of a bad PDF definition. A bad PDF definition constitutes of but is not totally comprised of Font embedding. Other errors can consist of messed up gamma values, etc which may result in the pictures looking different when viewed with different PDF Readers but lets not dwelve into those at the moment.
So how exactly is one supposed to embed fonts into an Acrobat pdf. If you’re using Adobe Acrobat Distiller, instructions can be found here. In case you’re using GhostScript, you can find help here. It can be implied that the types of font one should use should be embeddable, e.g. TrueType or Type1.
At this point you may be wondering about what to do if you have a document that does not have fonts embedded into it. Generally PDF Viewers can be supplied with font file paths so that they can pick font definitions from there. So you just need a comprehensive collection of fonts on your system.
Where does one get a collection of fonts to use. Printers use postscript to define documents and they contain a collection of common fonts to render page output correctly. I extracted some fonts out of some Lexmark printer drivers once. I’ve uploaded them and they can be downloaded here.
In ghostscript, the font file directory can be specified as follows[following extract copied blatantly from here]:-
1) Symbolic link to the font directory as the expected dir for example:
ln -s /usr/local/share/ghostscript/fonts app/ghostscript-8.00/share/ghostscript/fonts
2) Tell gs where to find the fonts using the -I option to add a search path. For example:
gs -I/usr/local/share/ghostscript/fonts …
3) Set the GS_LIB environment variable to specify the dir:
Please let me know in the comments if any of these links particularly to the compressed fonts file dies.