ページ分割がうまく機能しない

テーマを制作中なのですが、カテゴリーアーカイブでのページ分割がうまく機能せず困っています。（next_posts_link();のリンクで飛んでも404が出てしまう）
個別エントリーでは問題なく機能するのですが。

色々やってみた結果、パーマリンクの設定をデフォルト（wp/?cat=1）にすると問題なく動くことが判明しました（wp/?cat=1&paged=2）。
使用したいパーマリンクの設定は「/%category%/%postname%/」なのですが、これだと使用できないのでしょうか？