Ubuntu 12.04 LTS (64-bit) に Adobe Reader 9.5.5 をインストールしたら、検索ボックスに日本語を直接入力した時に文字化けが発生するので困っていたのですが、環境変数に CHARSET=eucJP を追加すれば文字化けしないことが分かりました。
管理者権限で、/opt/Adobe/Reader9/bin/acroread の export UBUNTU_MENUPROXY=0 の下ぐらいに export CHARSET=eucJP を追加するのが一番簡単だと思いますので困っていらっしゃる方はお試しください。
（ググっても同様の情報が見つからなかったので、ひょっとするとウチの環境が何かマズいのかもしれません。）