便乗ですいませんが、似たようなことが起きているので質問です。
パーマリンクをカスタム構造にして
/%category%/%postname%
で使用しています。
投稿スラッグは変更せず、日本語を使用して
http://example.jp/category/%82%d9%82%b0%82%d9%82%b0
とした場合
投稿画面の「この投稿を表示」をクリックしたらInternet Explorer 6でNot Foundになってしまいます。
URLを見るとURLエンコードが変更されているようでしたが、これはバグでしょうか。
firefox3,opera9.5.2ではちゃんと表示されました。
WordPressのバーションは2.6と2.6.1です。