Custom post type / taxonomy rewrite archive page 2 gives 404

Maybe echoing the last query will help debug the problem.
Paste this on your 404 page:

global $wpdb;
echo "<pre>";
var_dump($wpdb->last_query);
die();