Don’t use query_posts. This is a classic example of what happens when you do 🙂
Basically, when WordPress receives an url, it interprets this as a query – it then queries the database to find the results (if any) and serves up an appropriate template (such as 404.php in the case of no results).
If it happens to reach your template page – it’s then told to discard that query, and start a new one (which is wasteful) and will break pagination.
Basically pagination adds the paged query variable to the current url – this new url (which should take you to page 2, say) – forms the basis of the query to recieve page 2 – but the url in the address bar isn’t the content you are after (because you discard that and start a new query with query_posts. The end result is that a query, that you don’t really want, is performed and turns up no results, so the 404 template is served and the template with your query_posts is never reached.
Have a look at the above linked post for alternatives to query_post, but as this is the ‘main query’ (the query based on the recieved url) you want to be using pre_get_posts.