不具合とその原因
カテゴリ毎の一覧ページで2ページ目以降をクリックすると、404 not foundとなり、表示されません。トップ、タグ、検索ページ、アーカイブページは問題はありませんでした。
原因をいろいろ調べてたところ、WP-Pagenaviに問題がある訳ではなく、Wordpressのパーマリンクによるバグらしいです。
上記のリンク先にもありますが、パーマリンクを「%category%/%postname%」 に設定した場合、カテゴリー一覧ページでのページ送りがうまくいかないというバグのようです。記載内容を引用させてもらうと
このバグは、カテゴリーリストの2ページ目が cat-name/page/2 みたいなURLになったときに404エラーを返すというもの。というのもWordPressは、カテゴリーリスト表示のリクエストが投げられたとき、 post_typeが「post」になっている記事だけをデータベースから引っぱってくるからなんです。
このサイトはパーマリンクを「%category%/%postname%」にカスタマイズしていたので、まさにその通りでした。
解決方法
この問題を解決するプラグインが2つあり、一つはうまくいきませんでしたが、参考のために両方紹介しておきます。
もともとは「Top Level Categories」という、URLに表示される「category」の文字を消すプラグインの不具合解消のために作られたものです。このサイトでは「Top Level Categories」は使用していませんが、現象が非常に似ていたので試してみると、見事解決しました。
「不具合とその原因」で紹介した鉄王さんの記事にもありますが、インストールすることで解決するようです。しかし、原因は不明ですが、このサイトでは解消されませんでした。
とりあえず解決して何よりです。同じ様な現象に困っている方は、是非参考にして下さい。