検索しようとする文字列が文字化け

はじめまして。

文字コードに関することだと思い、インストール方法に問題があるのかもしれず、
こちらでアドバイスいただければと思い、投稿しました。

症状は、
全角文字でブログ内を検索したら、その文字列が文字化けしてしまうようで、ヒットしません。
半角文字なら、正しく検索できます。

結果画面のSearch欄には、検索に用いた文字列をそのまま表示されるようになっているのですが、
検索実行後に、Search欄の文字が化けてしまっているんです。

たとえば、「どうなるんだ」と検索したら、
結果画面のURLは、
　　http://www.hogehoge.com/?s=どうなるんだ
となっており、
Serach欄には、 縺ｩ縺 という化けた文字が表示され、当然ヒットもしないんです。

プラグインを全部OFFにしても、デフォルトテーマや他のテーマにしても、同じ現象でした。
なので、インストールした時点から、実はこういう現象になっていたのではと思い、
何らかの対処方法をがあれば、アドバイスいただければ嬉しいです。

環境は、以下の通りです。

OS: 　　　Windows Vista
Server: Vertrigo (Apache、PHP、MySQLがセットで導入できるアプリケーション）
データベースに指定している文字コード: UTF-8 照合順の設定は、utf8-general-ci
ワードプレスで指定している文字コード: UTF-8

他に必要な情報があれば、それもご指摘いただければありがたいです。
どうぞ、よろしくお願いします。