Category page for custom-taxonomy shows 404 when using custom permalink structur

I’m having a small issue with category pages for a custom taxonomy when custom permalinks are used, and I was wondering if someone might be able to help out and point out where I’m going wrong.

I’ve created a taxonomy “Brands” for use with a custom post type (in this case, Products), using the code below place in the functions.php file of the theme. I’ve created a page template for the Brands page, which lists all the brands using the wp_list_categories($args) template tag, and that’s all fine.

Now, if I use WordPress’ default permalink settings (where you get urls ending with ?page_id=7 and similar), clicking on any of those brands in the list, takes you to a category page which lists all the products for that brand – which is exactly the intent. If however, I set any other custom permalink structure (say /xyz/%postname%/ ), when you click on the brand name I get the 404 page instead of the category page (the same also happens when clicking view on a Brand when viewing the list within the WordPress admin).

I’ve checked various guides on making custom taxonomies, and have tried to be very careful with setting the rewrite for the taxonomy, and now I’m at a loss as to what the issue is. Any help will be much appreciated.

add_action( 'init', 'build_taxonomies', 0 );

function build_taxonomies() {  

register_taxonomy(
    'brand',
    'products',
    array(
    'labels' => array(
        'name' => 'Brands',
        'singular_name' => 'Brand',
        'search_items' => 'Search Brands',
        'popular_items' => 'Popular Brands',
        'all_items' => 'All Brands',
        'parent_item' => 'Parent Brand',
        'parent_item_colon' => 'Parent Brand:',
        'edit_item' => 'Edit Brand',
        'update_item' => 'Update Brand',
        'add_new_item' => 'Add New Brand',
        'new_item_name' => 'New Brand Name'
        ),
        'hierarchical' => true,
        'public' => true,
        'show_ui' => true,
        'sort' => true,
        'query_var' => true,
        'args' => array('orderby' => 'term_order'),
        'rewrite' => array('slug' => 'brands', 'with_front' => false),
    )
);
}