The $wp_rewrite->wp_rewrite_rules() function returns an array of rewrite rules but the order of these rules is a problem. The problem is the last rule on the server that works is:
[(.+?)/?$] => index.php?category_name=$matches
This rule catches everything, the problem is that this rule is not the last rule returned and as a result the rules after it are not processed, and the url_to_postid() function incorrectly returns 0 which causes the 404 handler to fail.