Sometimes you need font types embedded into your document, here is a good solution:
http://mohamednabeel.blogspot.pt/2009/10/fixing-font-not-embedded-issue-to-pass.html
Since I personally use kile to edit LaTeX documents, I process normally to create the .dvi, and then I use the commands
> dvips -Ppdf -G0 -tA4 file.dvi
> ps2pdf -dCompatibilityLevel=1.4 -dPDFSETTINGS=/prepress file.ps file.pdf