Ubuntu Hardyでも経験はしたのだが、PDF内にフォントを内蔵していないPDFをUbuntuの文書ビュア(evince)で表示すると、日本語部分がトーフ（□）になってしまう。
具体的には、こういうPDFがダメ
Hardyの頃は poppler-data パッケージをインストールしてやれば解消できたのだが、Lucidではだめ。
https://wiki.ubuntulinux.jp/JapaneseLocalizedDerivative/LaTeXForJapanese
↑ここにEvinceの文字化け対策 という項目があり、実際にLucidでも文字化けが解消したという情報もあるが、ダメ
最終的にはこちらの情報が該当した。
「NattyにおけるEvinceの問題」
https://wiki.ubuntulinux.jp/Develop/Natty/Evince
原因は, /etc/fonts/conf.d/69-language-selector-ja-jp.confで表示に使用するフォントの選択を行っているのだが、これが正常に機能しておらず、フォントリストの先頭の"DevaVu(非日本語フォント)"が選択される結果、日本語部分がトーフに化ける、というもの。
http://web.archiveorange.com/archive/v/F78Lpv5TRmtNqrrB0eyo
↑こちらを見るとSRUとして申請をトライしてみるということなのですが、Lucidまで降りてくるかどうかは微妙なので自分で直してしまうのを推奨します。
以下パッチ
----
$ diff -u conf.avail/69-language-selector-ja-jp.conf conf.d/69-language-selector-ja-jp.conf
--- conf.avail/69-language-selector-ja-jp.conf 2011-04-13 22:48:26.093985086 +0900
+++ conf.d/69-language-selector-ja-jp.conf 2011-04-13 23:00:18.349516971 +0900
@@ -10,7 +10,6 @@
<string>serif</string>
</test>
<edit name="family" mode="prepend" binding="strong">
- <string>DejaVu Serif</string>
<string>Takao P明朝</string>
<string>IPA P明朝</string>
<string>IPA モナー P明朝</string>
@@ -28,7 +27,6 @@
<string>sans-serif</string>
</test>
<edit name="family" mode="prepend" binding="strong">
- <string>DejaVu Sans</string>
<string>Takao Pゴシック</string>
<string>IPA Pゴシック</string>
<string>IPA モナー Pゴシック</string>
----
2箇所だけなので手patchしてもよし。