Ktai Style 1.30 で title タグの文字化け発生

Firefox2 の Useragentswitcher を使用して調査したところ、生成されるHTMLの <title> タグ内にある日本語が文字化けしていることがわかりました。
念のためブログのタイトルを半角英数のみに変更したところ正常に表示されましたので、文字コード変換に関する問題かと思います。

どんな URL でアクセスしても症状が出ますか? (特にシングルポスト)
あと、サイト名は具体的にどんな名前ですか? (Shift_JIS でバックスラッシュを含む文字かどうかが気になるところ)

1.21 と 1.30 では、デフォルトテーマをそのまま使っている場合は、title 回りのコードは同じです。テーマを改造して ks_wp_head() を有効にしている場合は動作が違ってくるかもしれません。そのへんはいかがでしょうか?

あと、念のため、サーバーの Apache, PHP, MySQL のバージョンを教えてください。

サイト名には、2バイト目に 5C を含む文字は使用していません。

いやだから、「具体的なサイト名」を書いていただきたかったのですが……。2バイト目に 0x5c が来るか来ないかは気になる点の1つですが、他の原因も十分考えられるため、その問題となっているサイト名そのものがぜひとも必要です。「不具合を再現させる」ためには、不可欠なことですので、ご協力をお願いします。
実のところ、一番欲しいのは、「文字化けした状態での HTML ソースコード」なのですが。

すでに書いた通り、バージョン 1.21 と 1.30 では、ks_title() 回りのコードは同じなので、バージョンダウンで正常動作するということは、非常に不可解です。ソースコードを見ると分かりますが、wp_title() の出力をほぼそのまま流用する仕組みなので、「Ktai Style の不具合」と言われても困ってしまいます。

またカテゴリへのリンク等、一部パーマリンクも正常に出力されませんでした。

これも謎ですね。ますます、その異常動作しているサイトを直接確認したいところです。パーマリンクは get_permalink() の出力から、ホスト名部分を削除するのですが、その削除がよくない可能性があります。もしくは、パーマリンクに & を含む場合、&#38; のかわりに &amp; を使うように変更しています (旧端末は &#38; を理解しないため)。

別トピックで出てきたのですが「All in One SEO Pack とコンフリクトする」のが原因かもしれません。
AIOSP を使用中止するか、上記リンク先にある対策コードを入れてみてください。