How to overwrite the category template in a plugin

I noticed that you’re using is_category() in your function, which means you’re targetting the default/core category taxonomy and not a custom taxonomy, hence you should instead use the category_template hook. E.g.

add_filter( 'category_template', 'load_new_custom_tax_template');
function load_new_custom_tax_template ($tax_template) {
    // I don't check for is_category() because we're using the category_template filter.
    return dirname( __FILE__ ) . '/templates/category.php';
}

Alternatively, you could use the template_include hook which runs after the <type>_template hook such as the category_template and taxonomy_template:

add_filter( 'template_include', 'load_new_custom_tax_template');
function load_new_custom_tax_template ($tax_template) {
    if (is_category()) {
        $tax_template = dirname( __FILE__ ) . '/templates/category.php';
    }
    return $tax_template;
}

Note though, other plugins can also override the template, hence you might want to use a lower priority, i.e. a greater number as the 3rd parameter for add_filter(). E.g. 20 as in add_filter( 'category_template', 'load_new_custom_tax_template', 20)