解決しました。

xpdf-commonをapt-getでインストール、
cmap-adobe-japan1を取ってきてdpkgでインストール、
さらに/etc/xpdf/xpdfrcに
include /etc/xpdf/xpdfrc-japanese.dpkg-new
を書き加えればOKでした。

apt-getしか使えない男にお付き合いいただきありがとうございました。
お邪魔しました。