WP_Query and Pagination

I am using WP_Query to call posts from a specific category as shown in the code below. I have also added pagination which is where the problem is....

<?php

            $temp = $wp_query;
            $wp_query= null;
            $wp_query = new WP_Query();
            $args = array(
                 'category__in' => array( 3 ),
                 'posts_per_page' => 3,
                 'paged' => $paged,
                 'order' => 'DESC',
            );
            $wp_query->query($args);
            $max_page = $wp_query->max_num_pages;

            while ($wp_query->have_posts()): $wp_query->the_post();  ?>

            <a href="<?php the_permalink() ?>" rel="bookmark" title="Permanent Link to <?php the_title_attribute(); ?>"><img src="<?php video_thumbnail(); ?>" class="recvidimg" /></a>

      <?php      endwhile;

$big = 999999999; // need an unlikely integer

echo paginate_links( array(
	'base' => str_replace( $big, '%#%', esc_url( get_pagenum_link( $big ) ) ),
	'format' => '?paged=%#%',
	'current' => max( 1, get_query_var('paged') ),
	'total' => $max_page
) );		

wp_reset_query();

			?>

Code (markup):

The pagination shows up and has the proper amount of pages in relation to the number of posts. However, anything passed page 2 shows a "page not found"

 

Why don't u try some plugins? there are many plugins can do that? I'm using Wp-PageNavi for my website. It's great!