Почему taxonomy_exists возвращает false?

Потому что вы сначала проверяете наличие таксономии, и потом только ее создаете. Поставьте выше объявление функции add_new_taxonomies() и вызов хука.

<?php
function add_new_taxonomies() { 
    /* создаем функцию с произвольным именем и вставляем 
    в неё register_taxonomy() */    
    register_taxonomy('countries',
        array('post'),
        array(
            'hierarchical' => true,
            /* true - по типу рубрик, false - по типу меток, 
            по умолчанию - false */
            'labels' => array(
                /* ярлыки, нужные при создании UI, можете
                не писать ничего, тогда будут использованы
                ярлыки по умолчанию */
                'name' => 'Countries',
                'singular_name' => 'Country',
                'search_items' =>  'Search country',
                'popular_items' => 'Popular country',
                'all_items' => 'All countries',
                'parent_item' => null,
                'parent_item_colon' => null,
                'edit_item' => 'Redact country', 
                'update_item' => 'Refrash country',
                'add_new_item' => 'Add new country',
                'new_item_name' => 'New country name',
                'separate_items_with_commas' => 'Separate countries with commas',
                'add_or_remove_items' => 'Add or remove countries',
                'choose_from_most_used' => 'Choose from most used',
                'menu_name' => 'Countries'
            ),
            'public' => true, 
            /* каждый может использовать таксономию, либо
            только администраторы, по умолчанию - true */
            'show_in_nav_menus' => true,
            /* добавить на страницу создания меню */
            'show_ui' => true,
            /* добавить интерфейс создания и редактирования */
            'show_tagcloud' => true,
            /* нужно ли разрешить облако тегов для этой таксономии */
            'update_count_callback' => '_update_post_term_count',
            /* callback-функция для обновления счетчика $object_type */
            'query_var' => true,
            'show_admin_column'     => true,
            /* разрешено ли использование query_var, также можно 
            указать строку, которая будет использоваться в качестве 
            него, по умолчанию - имя таксономии */
            'rewrite' => array(
            /* настройки URL пермалинков */
                'slug' => 'country', // ярлык
                'hierarchical' => true // разрешить вложенность

            ),
        )
    );
}
add_action( 'init', 'add_new_taxonomies', 0 );

$parent_term = taxonomy_exists('countries');
var_dump($parent_term);