Check the 3rd and 4th parameters for previous and next_post_link:
in_same_term
(boolean) (optional) Indicates whether next post must be within the same taxonomy term as the current post. If set to ‘true’, only posts from the current taxonomy term will be displayed. If the post is in both the parent and subcategory, or more than one term, the next post link will lead to the next post in any of those terms.
true
false
Default: false
excluded_terms
(string/array) (optional) Array or a comma-separated list of numeric terms IDs from which the next post should not be listed. For example array(1, 5) or ‘1,5’. This argument used to accept a list of IDs separated by ‘and’, this was deprecated in WordPress 3.3
Default: None
Also, you may find creating custom taxonomy types better for use with CPT’s than categories.
add_action( 'init', 'video_type_taxonomy' );
function video_type_taxonomy() {
register_taxonomy( 'video-type', 'video',
array(
'labels' => array(
'name' => _x( 'Types', 'taxonomy general name', 'executive' ),
'add_new_item' => __( 'Add New Video Type', '$text_domain' ),
'new_item_name' => __( 'New Video Type', '$text_domain' ),
),
'exclude_from_search' => true,
'has_archive' => true,
'hierarchical' => true,
'rewrite' => array( 'slug' => 'video-type', 'with_front' => false ),
'show_ui' => true,
'show_tagcloud' => false,
)
);
}