I've got a category titled News and a bunch of posts which are assigned to this category.
I can browse to domain/news and view 10 posts. When browsing to the next page, the URL is domain/news/page/2/ but this displays a Page Not Found error.
I have WP-PageNavi installed and this is showing 4 pages that I should be able to browse to, but each of them returns a Page Not Found error.
Why is WordPress not displaying the next set of 10 posts when I have 37 in this category?
This guy had the same problem than you and was able to fix the problem: http://wordpress.org/support/topic/loops-and-wp-pagenavi-plugin-problems
This seems silly, but have you tried flushing the url cache... Settings->Permalinks Then click "Save Changes" (Each time you do this Wordpress will reset permalinks internally).
I like to do that first before I continue troubleshooting pagination issues. Assuming you aren't using any custom post types or taxonomy, this is usually due to the $paged global not being passed in a custom page query.
<?php
$paged = (get_query_var('paged')) ? get_query_var('paged') : 1; //The global
$sticky=get_option('sticky_posts');
$args=array(
'cat'=>3,
'caller_get_posts'=>1,
'post__not_in' => $sticky,
'paged'=>$paged,
);
query_posts($args);
?>