Problem with add_rewrite_rule and pagination (paged and page query_vars)

I have a custom taxonomy named location and I want to add sections like ‘news’ and ‘marketplace’ for each term, so my url looks like /location/montreal/news/

It works perfectly until I try to add pagination. Here is my code :

add_action( 'init', 'region_rewrite' );
function region_rewrite()
{
    global $wp;
    $wp->add_query_var( 'section' );

    add_rewrite_rule(
      '^location/([^/]*)/([^/]*)/page/([0-9]+)/?',
      'index.php?location=$matches[1]&section=$matches[2]&paged=$matches[3]',
      'top'
    );
    add_rewrite_rule(
      '^location/([^/]*)/([^/]*)/?',
      'index.php?location=$matches[1]&section=$matches[2]',
      'top'
    );
}

I’m using the Rewrite analyser plugin and it seems that the query_vars location, section and paged are assigned with the right value. However, I get a 404 error when trying to access a page url like /location/montreal/news/page/2. I also noticed that the the page variable has the value /2. Is it possible that this is why I’m getting a 404 not found ?

Any help would be greatly appreciated!

I believe you could just call the paged add_rewrite_url last so that it is checked first. Otherwise the paged version will never get any match, since the non-paged one will always match first. Should also work if you remove ‘top’ from your arguments.

Also, check out this page for a nice way of debugging those 404 when working with custom rewrite:
http://www.dev4press.com/2012/tutorials/wordpress/practical/debug-wordpress-rewrite-rules-matching/