I got exactly the same pb like you. I am investigating fonts, as I am suspecting that "ghostscript" does not have enough Type1 fonts to render the eventually refered fonts from the pdf file.
As i you print a pdf including ttf fonts without any chance for the viewer (ghostscript, or ps, or gv) to acces to the description of the fonts.
I would appreciate if anyone could confirm (or not), and could give some advice. This is painfull here...