I needed a way to have my theme blog posts all under /blog/ and all custom post types have their slug right off the root of the site.
By default, when I update the permalinks structure in the wp-admin to be /blog/%postname%/ all the custom post types got prepended with /blog/.
To fix this I updated the custom post type options when I register the post type in functions.php to:
'rewrite' => array( 'with_front' => false )
This fixed the issue and now all your permalinks are belong to us.