Plugins seems to work fine. It seems this is particular when CPT is used in a theme. I can’t find another theme with CPT but if you find any, please do test it. I used another custom post type code on a different theme and permalinks still show 404 for me.
add_action( 'init', 'register_cpt_gallery' );
function register_cpt_gallery() {
$labels = array(
'name' => _x( 'Galleries', 'gallery' ),
'singular_name' => _x( 'Gallery', 'gallery' ),
'add_new' => _x( 'Add New Gallery', 'gallery' ),
'add_new_item' => _x( 'Add New Gallery', 'gallery' ),
'edit_item' => _x( 'Edit Gallery', 'gallery' ),
'new_item' => _x( 'New Gallery', 'gallery' ),
'view_item' => _x( 'View Gallery', 'gallery' ),
'search_items' => _x( 'Search Galleries', 'gallery' ),
'not_found' => _x( 'No galleries found', 'gallery' ),
'not_found_in_trash' => _x( 'No galleries found in Trash', 'gallery' ),
'parent_item_colon' => _x( 'Parent Gallery:', 'gallery' ),
'menu_name' => _x( 'Galleries', 'gallery' ),
);
$args = array(
'labels' => $labels,
'hierarchical' => false,
'supports' => array( 'title', 'editor', 'excerpt', 'author', 'thumbnail', 'custom-fields', 'comments', 'revisions' ),
'taxonomies' => array( 'category', 'post_tag', 'collections', 'gallery_tags' ),
'public' => true,
'show_ui' => true,
'show_in_menu' => true,
'show_in_nav_menus' => true,
'publicly_queryable' => true,
'exclude_from_search' => false,
'has_archive' => true,
'query_var' => true,
'can_export' => true,
'rewrite' => true,
'capability_type' => 'post'
);
register_post_type( 'gallery', $args );
}