This is isn't pretty, as the problem is that unless you specify category(s) (or tag(s)), WordPress won't query the terms tables at all, so there is no way to sort by category ID. And even if you do specify categories, you can't just pass an "order by" query variable to query_posts, as WordPress restricts what can come from a query variable and be used in the "order by" clause.
Basically, the code below sets up filters to add a "join" clause to include the terms tables in the query, to restrict it to categories (not paying attention to tags), and then to sort by the category ID. And then it re-queries, using the existing query variables (such as page number, etc.). Your mileage may vary.
<?php global $wp_query;
add_filter('posts_join', create_function('$a', 'global $wpdb; return $a . " INNER JOIN $wpdb->term_relationships ON ($wpdb->posts.ID = $wpdb->term_relationships.object_id) INNER JOIN $wpdb->term_taxonomy ON ($wpdb->term_relationships.term_taxonomy_id = $wpdb->term_taxonomy.term_taxonomy_id) ";'));
add_filter('posts_where', create_function('$a', 'global $wpdb; return $a . " AND $wpdb->term_taxonomy.taxonomy = \'category\'";'));
add_filter('posts_orderby', create_function('$a','global $wpdb; return "$wpdb->term_taxonomy.term_id ASC";'));
query_posts($wp_query->query_vars);
?>
<?php while ( have_posts() ) : the_post() ?>