以下のようなケースのとき、404NotFoundが起こる原因と解決法について簡単に記します。
http://example.com/taxonomy-name/page/2/



例えば、このように1記事ごとにページが区切られるようにしてページ送りを確認しているとき

query_posts( 'posts_per_page=1' );?>

このときに「next_posts_link」などを使って404NotFoundになる原因は、

[設定] -> [表示設定] -> 1ページに表示する最大投稿数 がページ送りの判定に使われているからです。

ここをposts_per_pageと同じ数値にすると、解決します。