Rewrite Rule & Regex - Extract 'cat-name' and 'page-number' from http://domain.com/custom-post-type/category/cat-name/page/page-number

I have an URL formatted so:

http://domain.com/custom-post-type/category/cat-name/page/page-number

I need to extract:

cat-name and page-number

So that in my functions.php, I can create the custom rewrite rule:

function my_insert_rewrite_rules( $rules ) {
  $newrules = array();
  $newrules['projects/category/(.+)/page/(\d+)/?$'] = 'index.php?post_type=projectproject_cat=$matches[1]paged=$matches[2]';
  return $newrules + $rules;
}

I am trying to use the expression:

projects/category/(.+)/page/(\d+)/?$

Which seems to work appropriately (escaping the forward slashes) in this example: http://rubular.com/r/5rzECsTexy

However, this never seems to work, the URL:

http://domain.com/projects/category/print and http://domain.com/projects/category/print/page/2 always seem to 404.

My previous rewrite rule of projects/category/(.*/?)$ worked for the category, but did not pull the page number properly.

Edit Custom Post Type registration code (in my theme's function.php)

// Custom Post Types
add_action( 'init', 'create_post_type' );
function create_post_type() {
    register_post_type( 'project',
        array(
            'labels' = array(
                'name' = __( 'Projects' ),
                'singular_name' = __( 'Project' )
            ),
        'public' = true,
        'has_archive' = true,
        'taxonomies' = array('category'),
        'rewrite' = array('slug' = 'projects')
        )
    );
}