Donncha reporting on WP’s Trac. Looks like this effect is somehow to be expected though; from santosj:
I’m pretty sure it does say something about screwing up the main Loop. It also says that the alternative is to use get_posts() or create your own WP_Query object. You just can’t go around overriding globals and expecting stuff to work.
I think I’ve read this before and yeah, the safest bet is to create a new WP_Query object. That query_posts() is somehow picky, indeed. It might break your paging. Your next page link might be next. And then there’s many other different stories.
My point is, query_posts() is fine, it’s great to use when you want to do something different with your theme. But please, get to know her first.