［2013.9.12追記］
初出からずいぶんたって、今ではWordPress 3.3から登場した「pre_get_posts」フックを使う方法が主流となってきました。記事の後半にサンプルコードとともに追記しましたのでご参照ください。
［初出時のテキスト］
WordPress 3.0で導入された新機能の一つ「カスタム投稿タイプ」。本格的に使ってみようという段になって、思わぬ壁にぶつかってしまいました。「カスタム投稿タイプ」で作った投稿群をカテゴリアーカイブで表示したとき、ページ送り（ページネーション）つまり
http://www.example.com/archives/category/foo/page/N（Nは数字）
といったURIで表記されるページが404 Not Foundを返すのです。
結論からいうとこの問題、『Custom Post Type Category Pagination Fix』というプラグインで解消することができました。そこで、カスタム投稿タイプの設定やコードなども交えて、解決までの道のりを紹介しようと思います。同じような悩みでぶつかっている方のご参考になれば。