Page navigation doesn’t show when query category

Problem:
when I do www.example.com?cat=4 or choose category through custom menu or from category widget it shows only first page without navigation at the bottom, where it supposed to be. It’s the same if I use index.php or category-slug.php as template. For test, when I do www.example.com?year=2012 it works. Also, www.example.com?cat=4&paged=2 works. So it must be something with categories.

My setup:
Wordpress 3.5, Free WP tube theme, SQLite

Relevant code:
index.php

<?php get_header(); ?>

    <!-- code to get theme options and setup $orderby -->                               
                            query_posts($query_string.$orderby.'&cat=4'); //in this case showing category with navigation works
                            if (have_posts()) : ?>
                            <?php $i=0; while (have_posts()) : the_post(); $i++; ?>

                <!-- code for displaying posts -->          

                            <?php if($i%3==0) : ?><div class="clear"></div><?php endif; ?>

                            <?php endwhile; wp_reset_query(); ?>
                            <?php 
                            $next_page = get_next_posts_link('Previous'); 
                            $prev_pages = get_previous_posts_link('Next');
                            if(!empty($next_page) || !empty($prev_pages)) :
                            ?>
                            <!-- navigation -->
                            <div class="navigation">
                                <?php if(!function_exists('wp_pagenavi')) : ?>
                                <div class="alignleft"><?php echo $next_page; ?></div>
                                <div class="alignright"><?php echo $prev_pages; ?></div>
                                <?php else : wp_pagenavi(); endif; ?>
                            </div>
                            <!-- /navigation -->
                            <?php endif; ?>

Note: you can see I’m using the &cat=4 in query. It is the same as category_name=video because I want to show only videos on home page. But also, I want to make able to choose that category from custom menu in which case doesn’t show page navigation.

What I have tried:

Making $wp_query = null then making new query before the Loop.
http://wordpress.org/support/topic/next-page-navigation-doesnt-work.
Basically any variation of this

<?php
$myqueryname = $wp_query;
$wp_query = null;
$wp_query = new WP_Query();
$wp_query->query('showposts=5'.'&paged='.$paged);
?>

Doesn’t work.

Adding $paged as suggested by the creator of WP-pagenavi and forums:

<?php $paged = (get_query_var('paged')) ? get_query_var('paged') : 1; ?>
                                  <?php query_posts("cat=-11&paged='.$paged);; ?>

Doesn’t work.

Testings:
besides the simple ones in the “problem” part of the question i did print_r($wp_query) all the way to see where to problem starts and it starts right on the beginning, ie. when i put print_r($wp_query) as the first line in header.php. So, the problem is not in the custom query of the theme, am I right?
I did it for the working $wp_query and not working $wp_query then compared them.
This is the relevant comparison part of the code:
Working $wp_query:

[category_name] =>
[cat] => 4
...
**//most important part**
[found_posts] => 382    
[max_num_pages] => 43
...
[request] => SELECT SQL_CALC_FOUND_ROWS  wp_posts.ID FROM wp_posts  WHERE 1=1  AND wp_posts.post_type = 'post' AND (wp_posts.post_status = 'publish' OR wp_posts.post_status = 'private')  ORDER BY wp_posts.post_date DESC LIMIT 0, 9
...
//here shows code for some posts even if not displaying them, because they're not in the cat=4 or category_name=video 

non working $wp_query:

[category_name] => video
[cat] => 4
...
**//most important part**
[found_posts] => 1
[max_num_pages] => 1
...
[tax_query] => WP_Tax_Query Object
        (
            [queries] => Array
                (
                    [0] => Array
                        (
                            [taxonomy] => category
                            [terms] => Array
                                (
                                    [0] => video
                                )

                            [include_children] => 1
                            [field] => slug
                            [operator] => IN
                        )

                )

            [relation] => AND
        )
...
[query] => Array
        (
            [category_name] => video
        )

    [request] => SELECT SQL_CALC_FOUND_ROWS  wp_posts.ID FROM wp_posts  INNER JOIN wp_term_relationships ON (wp_posts.ID = wp_term_relationships.object_id) WHERE 1=1  AND ( wp_term_relationships.term_taxonomy_id IN (4) ) AND wp_posts.post_type = 'post' AND (wp_posts.post_status = 'publish' OR wp_posts.post_status = 'private') GROUP BY wp_posts.ID ORDER BY wp_posts.post_date DESC LIMIT 0, 9
...
//this $wp_query doesn't show code for the posts which are not from video category
...
[queried_object] => objArray Object
        (
            [term_id] => 4
            [name] => Video
            [slug] => video
            [term_group] => 0
            [term_taxonomy_id] => 4
            [taxonomy] => category
            [description] => 
            [parent] => 0
            [count] => 379
            [cat_ID] => 4
            [category_count] => 379
            [category_description] => 
            [cat_name] => Video
            [category_nicename] => video
            [category_parent] => 0
        )

Edit #1: This is the comparison BEFORE the custom query! When I dumped $wp_query inside the Loop, after the custom query_posts() they are identical. So the problem is not in the $wp_query.
Also, from the index.php code get_next_posts_link('Previous') returns NULL when choose category form menu or ?category_name=video

Conclusion:
something is happening before the template files with default query, but I don’t know what. Can somebody help me to show page navigation?

Edit #2: Since the get_next_posts_link('Previous') returns NULL I knew it’s something about the $wp_query->max_num_pages; That number must be bigger than 1 to show navigation. So i tested by putting code <pre><?php echo $wp_query->max_num_pages; ?></pre> to see when it changes from 1 to >1. I discovered that in working version it changes after the <?php endwhile; wp_reset_query(); ?> and in non working it doesn’t change.