I tested the custom post type with “Custom Post Type UI” plugin in order to help you. Capability type was set to ‘page’. Such custom post type is unavailable to user without ‘edit_pages’ capability as expected. Open “Admin Menu” for the ‘Administrator’ role and look, what real capabilities are in use to protect your custom post type.
Some mistake takes place possibly if you define custom post type using PHP code and it takes default ‘post’ capability type then.