Попробуйте указать 'taxonomies' => array( 'category' ) :
add_action( 'init', 'register_post_type_init' );
function register_post_type_init() {
$labels = array(
'name' => 'Видео',
'singular_name' => 'Видео',
'add_new' => 'Добавить видео',
'add_new_item' => 'Добавить новое видео',
'edit_item' => 'Редактировать видео',
'new_item' => 'Новое видео',
'all_items' => 'Все видео',
'view_item' => 'Просмотр видео на сайте',
'search_items' => 'Искать видео',
'not_found' => 'Видео не найдено.',
'not_found_in_trash' => 'В корзине нет видео.',
'menu_name' => 'Видеоновости'
);
$args = array(
'labels' => $labels,
'public' => true,
'show_ui' => true,
'has_archive' => true,
'menu_icon' => 'dashicons-video-alt3',
'menu_position' => 20,
'supports' => array( 'title', 'editor', 'comments', 'author', 'thumbnail'),
'taxonomies' => array( 'category' )
);
register_post_type('video', $args);
}