This problem is not related directly to the user permissions. But comes from how WordPress checks if user has access to the an admin page. WP checks if user has access to the admin menu item correspondent to the admin page, but if it’s not defined shows the access error message event if user has full access to this custom post type.
at the end of wp-admin/includes/menu.php:

if ( ! user_can_access_admin_page() ) {

	 * Fires when access to an admin page is denied.
	 * @since 2.5.0
	do_action( 'admin_page_access_denied' );

	wp_die( __( 'Sorry, you are not allowed to access this page.' ), 403 );

$menu = add_menu_classes( $menu );

You can find function user_can_access_admin_page() at wp-admin/includes/plugin.php file and look how many criteria WP checks for admin page access, not only related user capability.

You need to investigate how correctly define admin menu to show custom post type from there, not from the default WP menu for CPT. May be look to some other plugin code, which make something similar.