When using pdflatex to create pdf documents from latex input files, the embedded fonts are not generated when necessary. I attached a sample document, that shows this behaviour. The fonts are only generated when running latex -> dvips, after that they can be included into the document.
Created attachment 92871 [details] example tex file
Well, the information provided aren't sufficient to debug the problem; do you use tetex-2 or 3? have you added the mapfile to dvips, pdftex and dvipdfm config files for the embedding of the fonts?
removed from the tree, wontfix