Custom Post Type Pagination 404 Error

Fellas,

I have this problem with custom post type pagination where after I upgraded to WordPress 3.4/3.5, my pagination links just stopped working. I’ve tried searching the forum and the web for a related answer but non worked for my case. Also, I am not sure if it has to do with url rewrite, but anyhooo, here’s my front-page.php code..

<?php get_header(); ?>
    <div class="wrap">
        <?php
            $wp_query = new WP_Query( array('post_type' => 'gallery','posts_per_page' => 4, 'paged' => $paged ) );
        ?>
        <ul id="thumbs">
            <?php while (have_posts()) : the_post(); ?>
                <li>
                    <a href="<?php echo get_permalink(); ?>">
                        <?php echo get_the_post_thumbnail($post->ID,array(220,160)); ?>
                    </a>
                </li>
            <?php endwhile; ?>
        </ul>
        <div id="pagination">
            <?php
                $big = 999999999;
                $args = array(
                    'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
                    'format' => '?paged=%#%',
                    'current' => max( 1, get_query_var('paged') ),
                    'total' => $wp_query->max_num_pages
                );
                echo paginate_links( $args );
                wp_reset_postdata();
            ?>
        </div>
    </div>
<?php get_footer(); ?>

This works fine in WordPress 3.3 and this is the result I get:

WordPress 3.3

Request:
GET /gallery/?paged=2 HTTP/1.1

Response:
(Status-Line) HTTP/1.1 200 OK
Date Fri, 14 Dec 2012 15:02:28 GMT
Server Apache/2.0.64 (Win32) PHP/5.2.17
X-Powered-By PHP/5.2.17
X-Pingback http://localhost/gallery/xmlrpc.php
Content-Length 4617
Keep-Alive timeout=15, max=92
Connection Keep-Alive
Content-Type text/html; charset=UTF-8

And then it breaks in WordPress 3.4/3.5.. This is the result I get with 3.5:

WordPress 3.5

Request:
GET /gallery/?paged=2 HTTP/1.1

Response:
(Status-Line) HTTP/1.1 404 Not Found
Date Fri, 14 Dec 2012 15:06:04 GMT
Server Apache/2.0.64 (Win32) PHP/5.2.17
X-Powered-By PHP/5.2.17
X-Pingback http://localhost/gallery/xmlrpc.php
Expires Wed, 11 Jan 1984 05:00:00 GMT
Cache-Control no-cache, must-revalidate, max-age=0
Pragma no-cache
Content-Length 2908
Keep-Alive timeout=15, max=92
Connection Keep-Alive
Content-Type text/html; charset=UTF-8

Any help/ideas/troubleshooting tips would be greatly appreciated. This is the only piece of the puzzle I am trying to figure out to fit.

Thanks very mucho!