I looked at the WordPress 3.0 code. The behavior is caused by a change to how the redirect_canonical function handles categories, tags and taxonomies in wp-includes/canonical.php.
I don’t know the code well enough to know if this is a good fix, but I moved a section of the 3.0 code that deals with taxonomy to inside the is_tax() if block, and things seem to work fine now.
The original 3.0 code looks like:
if ( is_category() ) {
$redirect['query'] = remove_query_arg( array( 'category_name', 'category', 'cat'), $redirect['query']);
} elseif ( is_tag() ) {
$redirect['query'] = remove_query_arg( array( 'tag', 'tag_id'), $redirect['query']);
} elseif ( is_tax() ) { // Custom taxonomies will have a custom query var, remove those too:
$tax = get_taxonomy( $obj->taxonomy );
if ( false !== $tax->query_var)
$redirect['query'] = remove_query_arg($tax->query_var, $redirect['query']);
else
$redirect['query'] = remove_query_arg( array( 'term', 'taxonomy'), $redirect['query']);
}
$tax_url = parse_url($tax_url);
if ( ! empty($tax_url['query']) ) { // Custom taxonomies may only be accessable via ?taxonomy=..&term=..
parse_str($tax_url['query'], $query_vars);
$redirect['query'] = add_query_arg($query_vars, $redirect['query']);
} else { // Taxonomy is accessable via a "pretty-URL"
$redirect['path'] = $tax_url['path'];
}
I updated the bottom chunk of code that deals with tax_url to be inside the elseif (is_tax()) block.
if ( is_category() ) {
$redirect['query'] = remove_query_arg( array( 'category_name', 'category', 'cat'), $redirect['query']);
} elseif ( is_tag() ) {
$redirect['query'] = remove_query_arg( array( 'tag', 'tag_id'), $redirect['query']);
} elseif ( is_tax() ) { // Custom taxonomies will have a custom query var, remove those too:
$tax = get_taxonomy( $obj->taxonomy );
if ( false !== $tax->query_var)
$redirect['query'] = remove_query_arg($tax->query_var, $redirect['query']);
else
$redirect['query'] = remove_query_arg( array( 'term', 'taxonomy'), $redirect['query']);
$tax_url = parse_url($tax_url);
if ( ! empty($tax_url['query']) ) { // Custom taxonomies may only be accessable via ?taxonomy=..&term=..
parse_str($tax_url['query'], $query_vars);
$redirect['query'] = add_query_arg($query_vars, $redirect['query']);
} else { // Taxonomy is accessable via a "pretty-URL"
$redirect['path'] = $tax_url['path'];
}
}
So I think WordPress needs to be updated and not the plugin.