カテゴリの次ページなのにindex.phpが読み込まれる。

上記プラグインで解決しなかったので、下記方法で強引に解決しました。

wp-includes/link-template.phpの1461行目（Ver.3.5の場合）

■旧
$request = ( ( !empty( $request ) ) ? trailingslashit( $request ) : $request ) . user_trailingslashit( $wp_rewrite->pagination_base . "/" . $pagenum, 'paged' );

■新
$request = (user_trailingslashit( $wp_rewrite->pagination_base . "/" . $pagenum, 'paged' ));

この変更は質問者さま同様、カスタムパーマリンクを使っている方のみ有効です。
デフォルトでは逆に動かなくなると思いますのでご注意ください。

雑な解決方法ですが、わたしも同じ不具合に悩まされ、
急ぎだったのでソースごと改変しました。

あまりいい方法ではないと思いますので、
上記プラグインでうまく行かなかった方のみ、
バックアップをとった上、自己責任でお試しください。