Adobe社のサイトから最新のAdobe Readerをダウンロードしてインストールすれば解決しました。
ちなみにAdobe Readerのバージョンは初期状態では7.0.9で、最新版は2009年8月の現在は9.1.2です。
まず、Adobeのサイトhttp://get.adobe.com/jp/reader/otherversions/へ行き、オペレーティングシステムは Linux - x86 (.deb) , 言語は日本語を選択し、最新のAdobe Reader 9.1.2 をダウンロードします。
ダイアログがでて、プログラムで開くとかファイルを保存するとか選べるので、「ファイルを保存する」を選んでOKします。
Ctrl-Alt-tを押してターミナルを開いて ls コマンドを打つとたぶんAdbeRdr9.1.2-1_i386linux_jpn.debというファイルがあると思います。
そこで次のコマンドを打つと自動でインストールしてくれます。
sudo dpkg -i AdbeRdr9.1.2-1_i386linux_jpn.deb
これで文字化けせずにPDFが見れるようになるはずです。ターミナルでacroreadというコマンドで使うことができます。
acroread
またはacroread ファイル名.pdf
以下の記事のコメント欄を主に参考にさせていただきました。ありがとうございます。
http://eeepc.cocolog-nifty.com/blog/2009/02/xandros17-0dd6.html