I had a similar problem recently and determined the cause to be that when WordPress queries for posts in a category, it looks for posts with post_type equal to ‘post’ before it reaches the point where you query for post_type ‘any’ or some custom post type. This doesn’t cause a problem on page 1 because even if there are no posts it calls your template. However on page 2 and so forth, it doesn’t find any posts of post_type ‘post’ so it loads the 404 template before your template even gets a chance to modify the post_type parameter.
Is this a bug? That’s a good question. I would say so because you should expect that if you register the ‘category’ taxonomy on other post_types, all post_types would show up in that archive, not just strictly posts.
Hopefully that helps.