query_posts() for WordPress can be very handy when you want to control the contents. There is the posts_nav_link() links that works just fine, but the paginated function works great when you have quite a few posts to pull. So to start with the generic query code.
So there is the custom query and the main query loop in the start. And by default, WordPress uses the main query to determine pagination, and when you use a custom query, you create a new and entirely separate query.
And what happens is that even though you have paginated links, the link just loops to the same page. The solution was rather simple for this. Passing correct parameter for pages to the custom query like shown here:
At the end of the query, add wp_reset_query(); to make sure to reset the loop.
///Tested on Version 3.9.1