WordPress Custom Post Type Category Page

You are doing everything right, double check the below code and make sure to go to Permalinks in your dashboard to flush the rewrite rules.

From WordPress Codex:

Note: Visiting the Permalinks screen triggers a flush of rewrite rules. There is no need to save just to flush the rewrite rules.

It will work, I tested it using the below code:

Put the following in your functions.php:

add_action( 'init', 'create_custom_posts' );
function create_custom_posts ()
{      
    register_post_type( 'tutorials',
        array(
            'labels' => array(
                'name' => __( 'Tutorials' ),
                'singular_name' => __( 'Tutorial' )
            ),
        'public' => true,
        'supports' => array ('title', 'editor', 'thumbnail')
        )
    );

    register_taxonomy(
        'tutorial_categories',
        'tutorials',
        array(
            'labels' => array(
                'name' => 'Tutorial Categories',
                'add_new_item' => 'Add New Tutorial Category',
                'new_item_name' => "New Tutorial Category"
            ),
            'show_ui' => true,
            'show_tagcloud' => false,
            'hierarchical' => true,
            'hasArchive' => true
        )
    );
}

Create taxonomy-tutorial_categories.php, add a taxonomy category called php from the dashboard, and visit {yourwebsite.com}/tutorial_categories/php/. Works like a charm.