I've got a confusing mess on my local test site. I used several different plugins to create custom post types and then custom taxonomies. Then I found Query Multiple Taxonomies, which is ideal for what I'm doing. I tried it and it worked. So I continued to develop the site and get the data uploaded into my custom post type.
Now that I have data loaded, I am using "Ultimate Post Type Manager" and "Ultimate Taxonomy Manager" and "Custom Post Archives". The QMT widget displays all the taxonomies, and even shows correctly in the sidebar the existing terms (links to click to drill down). But when I click any of the links I get the Nothing Found message on a page with the correct rewrite URL for that term (it's not the same as the link I clicked which has query variables). I've tried it without "Custom Post Archives" with the same result. I looked at the rewrites array and it looks like it should be generating the same syntax as the QMT links have.
Does it sound like a rewrite problem or does the custom post type have to be passed in? (I don't remember doing this before, but I might not have tested it with a custom post type.)