Have you tried KPDF or Acrobat's Reader? I have never had problems with these viewers.
Fonts in Linux is a not so easy to understand subject I think. Every distro has another way for handling fonts. I'm not sure your problem is a font problem; "it should just work"
Btw, XPDF is a somewhat 'old' program (at least it looks old
), so try another program.