はじめまして。
私も同じような経験がありますが、サポートデータベースに次のような記載があります。ご参考までに。
文書番号 : 220726
[作成した PDF ファイルのしおりが文字化けする]
http://support.adobe.co.jp/faq/faq/qadoc.sv?220726+002
記載中の追加情報に「段落がハードスペースから始まっている場合。」とありますが、別に先頭でなくてもハードスペースがあると文字化けするようです。
なお、私の経験ではFrameMakerで作成したPDFファイルを開くAcrobat(Readerを含む)によってもしおりの表示がまちまちなようでAdobe Acrobat 6.0 Professional で見ると正しく表示されているのに 5.0 や Reader で見ると文字化けしているようなケースもあるようです。
なんにしろやっかいですね。