I literally tried everything I could think of, and every solution the WordPress Codex gave to preserve pagination when using query_posts. Nothing worked.
http://codex.wordpress.org/Function_Reference/query_posts#Example_3 (read Example 3 and "preserving the original query")
A page would only show the 1st page of results, and clicking "next" or going to page/2 would throw a 404. Is this some kind of bug in 3.0.1 where the documented query preserving doesn't work?
Crazy workaround: I used a Page with a custom template where I defined my own $wp-query with a bunch of parameters, and pagination worked beautifully.
This workaround DOES NOT fix the original problem. Any ideas?