パーマリンクをカスタム設定するとカテゴリ一覧のページ送りで404

パーマリンクの設定を/%category%/%post_id%/とし、カテゴリの一覧を”http://example.com/category/”で表示させているのですが、そのページは正常に表示されますが、ページ送りをすると404になります。

リンクを”http://example.com/category/category/”とするとページ送りは正常に動きます。
また、パーマリンク設定をデフォルトにすると動きます。

他のフォーラムで解決していたように、.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

と書き込んでいますが、効果はありません。
他のテーマに変えてみたり、プラグインを停止してみたり、他のサイトで解決策として紹介されていたプラグインを入れてみたり、色々しましたが動作しません。

記入しているのは以下のコードです。

<?php next_posts_link(__('&laquo;')); ?>
<?php previous_posts_link(__('&raquo;')); ?>

確認ブラウザはMacのFIreFoxとSafariです。

パーマリンクのカスタム設定はこのまま使用したいので、とても困っています。
どうぞ宜しくお願いします！！