WP 3.1でカテゴリーベースを付けずにページネーションすると404エラーにな

自分のローカル環境でテストして、ちゃんとリンクされましたよ。
WordPress 3.1
パーマリンク設定　/%category%/%postname%/
WP No Category Base バージョン 0.7

ページナビゲーション（ページネーション）はこちらのサイトを参考に自作しました。
WP-PageNavi を使わずにナビゲーション表示
http://www.yuriko.net/arc/2008/07/26/navigation/

「ページネーション」部分のソースが鍵になると思いますが。
何かのプラグイン使ってるのでしょうかね？

うーん。
テーマ Twenty Ten (Ver 1.2) の loop.php （の一番最後に）下のコードを入れてみて、
カテゴリーアーカイブを表示させてみましたが、SWDさんと同じ状況を再現できません・・・。

<?php /* paging navigation */
global $wp_rewrite;
$paginate_base = get_pagenum_link(1);
if (strpos($paginate_base, '?') || ! $wp_rewrite->using_permalinks()) {
	$paginate_format = '';
	$paginate_base = add_query_arg('paged', '%#%');
} else {
	$paginate_format = (substr($paginate_base, -1 ,1) == '/' ? '' : '/') .user_trailingslashit('page/%#%/', 'paged');
	$paginate_base .= '%_%';
}

$pagination = array(
	'base' => $paginate_base,
	'format' => $paginate_format,
	'total' => $wp_query->max_num_pages,
	'mid_size' => 5,
	'current' => ($paged ? $paged : 1),
	'prev_text' => '&laquo; Previous',
	'next_text' => 'Next &raquo;'
	);

echo '<div class="page-navi">'."\n";
echo paginate_links($pagination);
echo '</div>'."\n";
?>

カテゴリーのスラッグが「cat-a」として、
2ページ目は http://www.exsample.com/cat-a/page/2/ になってます。
（他にプラグインは WP Multibyte Patch しか入れていません）

となると、「自前の環境」に問題の起きているテーマを適用して、
同じ現象が起きればテーマに問題があるのでしょうし、
そうで無ければサーバーなど他の要因が考えられます。
問題の切り分けを行ってどこに原因があるのか精査しましょう。

いずれにしても今回、問題が起きているのはWordPress本体が原因ではないので、
このトピックスも「バグ報告と提案」以外に移動してもらいましょう。