I had the same problem and since the OP did not post his solution here is what was the problem in my case and how it was solved:
I am using a custom posts_per_page value in query_posts() for my different categories (for news 5). In the wordpress options the setting for Blogs shown at most (Settings->Reading) was set to 10 (standart).
At this point I had exactly 120 posts. 120/10 -> page 12 and for some reason WordPress thinks that’s the end of the news and does not show any more pages even though there should be more with the posts_per_page=5 value.
Simple solution is to set the Blogs shown at most to 1 or the least value you have in use (in my case 5).
Hope this helps.
