Fonts are not embedded into a pdf?

This might not be the most relevant question for askubuntu, but I'll try to answer it nevertheless: You probably included graphics in your document that use the Helvetica font (a common example are the axis labels for figures created by Matlab), right? If you used Helvetica in your document (e.g. with \usepackage{helvet}), the Helvetica replacement Nimbus Sans L would be used instead.

Embedding the fonts from external figures is not possible at the moment (it should work if you make sure that the external figures embed the fonts themselves, though!).

Therefore, as suggested in the comments, the only solution seems to be to do a PDF->PS->PDF conversion, e.g.:

pdf2ps file.pdf file.ps
ps2pdf14 -dPDFSETTINGS=/prepress -dEmbedAllFonts=true file.ps file.pdf

Unfortunately, hyperlinks for example will not survive this transformation.

See this question on the (more relevant) tex.stackexchange sister site: https://tex.stackexchange.com/questions/10391/how-to-embed-fonts-at-compile-time-with-pdflatex

Another (I believe, better) alternative is to use ghostcript:

gs -q -dNOPAUSE -dBATCH -dPDFSETTINGS=/prepress -sDEVICE=pdfwrite -sOutputFile=${file}_FONTS-EMBEDDED.pdf ${file}.pdf

It is better because the resulting pdf is smaller and keeps a good behavior in text copying. In fact, this method embeds other fonts, in place of the original. But, the resulting pdf will have all fonts embedded. I found this method here.