Category Template for Custom Post Type

You should create a taxonomy template, not a category. I suspect that you have misunderstanding about categories, terms and custom taxonomies. I would suggest that you read my post on this particular subject here

Study the taxonomy template hierarchy in the linked page in your question

As for the 404 page, you most probably haven’t flushed your permalinks after adding your custom post type.

EDIT

I have missed the fact that your rewrites for both your custom post type and taxonomy is the same, which will 404 all taxonomy requests. Have a look at this recent post, it has a work around if you want to keep your slugs the same.

Here is the solution reposted by @JeremyLove. Change the code as needed and with your taxonomy and post type names. Also, important, flush your permalinks after making any changes to your code so that the new structures can be saved

function taxonomy_slug_rewrite($wp_rewrite) {
    $rules = array();
    // get all custom taxonomies
    $taxonomies = get_taxonomies(array('_builtin' => false), 'objects');
    // get all custom post types
    $post_types = get_post_types(array('public' => true, '_builtin' => false), 'objects');

    foreach ($post_types as $post_type) {
        foreach ($taxonomies as $taxonomy) {

            // go through all post types which this taxonomy is assigned to
            foreach ($taxonomy->object_type as $object_type) {

                // check if taxonomy is registered for this custom type
                if ($object_type == $post_type->rewrite['slug']) {

                    // get category objects
                    $terms = get_categories(array('type' => $object_type, 'taxonomy' => $taxonomy->name, 'hide_empty' => 0));

                    // make rules
                    foreach ($terms as $term) {
                        $rules[$object_type . "https://wordpress.stackexchange.com/" . $term->slug . '/?$'] = 'index.php?' . $term->taxonomy . '=' . $term->slug;
                    }
                }
            }
        }
    }
    // merge with global rules
    $wp_rewrite->rules = $rules + $wp_rewrite->rules;
}
add_filter('generate_rewrite_rules', 'taxonomy_slug_rewrite');