Custom post type permalinks breaking due to 3.1 bug fix

So I just updated a site to 3.1 that uses several custom post types.

When I had made the site I had not noticed at the time the $post_type parameter for register_post_type has to be in all lowercase letters! ( it was not well written in the codex but now it is bold).
http://codex.wordpress.org/Function_Reference/register_post_type#Parameters

My custom post types were registered with a capitol letter for instance “Rentals” instead of ‘rentals’. This was fixed in 3.1 thus any posts registered with upper case letters were totally broken in the back and front end.

I was able to go back into the function and change it to lowercase and then call another function to update the database with the new name before it fires thanks to a post on wordpress.org by dennis_f.

Here new function

if(!get_option('custom_type_updated')){
global $wpdb;
$wpdb->query("UPDATE $wpdb->posts SET post_type = 'custom-rental' WHERE post_type = 'Custom-Rental'");
update_option('custom_type_updated','true');
}

and here is the register re-written in lowercase

// Custom page template for rentals      -----------------
function Rental_register_post_type() {
    register_post_type( 'custom-rental', array(
        'public'        => true,
        'can_export'    => true,
        'has_archive'   => 'Rentals',
        'rewrite'       => true,
        'supports' => array(
                ** bunch of supports stuff
            ),
        'labels' => array(
            **bunch of labels
            )
        )
    );
}
add_action( 'init', 'Rental_register_post_type', 0 );

This did fix the major issue of broken custom post types BUT
the problem is now using a custom permalink structure breaks the custom post type ‘rentals’, only the default works.

For example www.example.com/?custom-rental=7-bedrooms works fine, but no custom permalink structure works, I have tried each type and cleared the .htaccess and just returns a 404.

Any ideas?