I've been struggling with this problem a while now so I'm giving in and asking for assistance.
So, I have a custom post type called 'product' - this custom post type is set up to use the 'category' taxonomy.
The first page of the category archive works fine - I have placed:
global $wp_query; query_posts( array_merge( array('post_type' => 'product'), $wp_query->query ) );
at the top of category.php in the template. When you go to page 2 however, it gives a 404.
From what I can tell this is because the query functions/template loader are making it a 404 before the post_type rule is seen because its not finding any 'posts' on page 2 of the archive.
I've tried adding hooks into functions.php to try to get the post_type recognised earlier with no success.