Pagenavi Plugin and Custom Post Type Navigation Error (404)

[admin]

I have a similar problem with this ( <a href="https://wordpress.stackexchange.com/questions/9593/custom-post-type-archive-with-pagination">https://wordpress.stackexchange.com/questions/9593/custom-post-type-archive-with-pagination</a> ) and can't really figure out what to do !

I have a custom post type name 'gallery' and I have created a template to show all 'gallery' items. The url is www.domain.com/gallery. I use WP_Pagenavi plugin. Whenever I try to go to page 2 or higher, the url becomes www.domain.com/gallery/page/2 and it returns a 404 page. I read everywhere about it and I guess it has something to do with rewrite rules, the query and whatever else!

I have tried adding

add_rewrite_rule( 'gallery/page/([0-9]+)/?$', 'index.php?pagename=gallery&paged=$matches[1]', 'top' );

The thing is that I don't want to change my permalinks structure which now is /%postname%/.

Here is my full code

        <?php

        $paged = (get_query_var('paged')) ? get_query_var('paged') : 1;
        $args = array(
            'post_type' => 'gallery',
            'paged' => $paged,
            'showposts' =>24
            ); query_posts($args);

        if ( have_posts() ) : while ( have_posts() ) : the_post(); ?>


                ...stuff here...

                <?php endwhile; endif; ?>


        <?php 
            wp_pagenavi( );
        ?>

and here is my functions.php code for the gallery

add_action('init', gallery);
function gallery() {
$args = array(
        'label' => __('Gallery'),
        'singular_label' => __(Gallery),
        'public' => true,
        'show_ui' => true,
        'capability_type' => 'post',
        'hierarchical' => false,
        'rewrite' => true,
        'supports' => array('title', 'editor', 'thumbnail', 'custom-fields')        
);

register_post_type( 'gallery' , $args );
add_rewrite_rule( 'gallery/page/([0-9]+)/?$', 'index.php?pagename=gallery&paged=$matches[1]', 'top' );
}

I am pulling my hair with this (grrrrr).
Thank you in advance !