PDF（ファイル自体）の中身の問題と思われますが如何でしょうか？
PDFファイルは作成した事が無いので詳細は不明ですが、同じ文字化けはHTMLでも再現されます。
所謂「タイトル」要素の後のmetaの文字コードが埋め込まれてると文字化けは確実に発生します。
又はファイル保存時の文字コードが適切で無い場合にも。
違うかな？

プロファイルやセーフモードというよりは、PDFファイルを開いた場合に起こることが多いですね。

Firefoxのセーフモードや新規プロファイルではどうなりますか？

[参考]
http://support.mozilla.com/ja/kb/%E3%83%97%E3%83%AD%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%81%AE%E7%AE%A1%E7%90%86


[補足]
バージョン系列が違う(3.5.*と3.6、3.0.*と3.5.*など)Firefoxで同じ(ひとつの)プロファイルを使いまわすと不具合の原因となる場合があります。
できれば、系列が違うときは、新しいプロファイルを作ることをオススメします。

FireFox3.6をWindows7環境で使うと文字化けが起こります。
しかも、文字化けするのはタイトルバーだけで、タブや本文は文字化けを起こさないため、文字エンコードで戻すことができないなど、まったく対処できず困っています。

これでは、プレビュー時にタイトル確認ができないなど、不都合が生じます。
そのため3.5に戻して様子を見ているのですが、タイトルバーだけ文字化けということは解消できないのでしょうか？