Having the same issue since upgraded to WP 3.0. This is caused by a new behaviour introduced with this version.
$query_string = str_replace('&category_name=all-posts', '', $query_string);
$query_string = str_replace('category_name=all-posts', '', $query_string);
$posts = query_posts($query_string);
WP 3.0 redirects non-existent pages to 404, so the code above in my template never runs.
