Change the Permalinks structure as you mentioned, but also add (or change) the following line for all the other CPTs:
$rewrite->with_front="false";
Setting with_front to false will strip off whatever prefix you have listed in your Permalink settings.
If setting that up and hitting the Permalinks page to flush rewrite rules doesn’t immediately fix the problem, you might need to call unregister_post_type() for each existing CPT before re-registering them, as they can get cached pretty hard in some cases.