パーマリンク設定

何度もこのフォーラムで話題になっているパーマリンク設定ですが、ウチのサーバーでもWPを2.8にアップデートした後から使えなくなってしまいました。具体的にはパーマリンク設定を
/%category%_%post_id%.html
とした時に、全てのページがリンク切れになってしまいます。（デフォルト設定は使用できます。）

サーバーはトクトクです。
.htaccessには
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>
# END WordPress

のように記述し、UTF-8+LFで、アスキーモードでwp-config.phpと同じ階層にアップロードしています。
過去ログを読んで、いろいろ試してみたのですがダメでした。
どうかアドバイスをお願いいたします。