This has been driving we crazy for a while as well, although I made a tweak that seems to get it working. The above code didn't work for me either, but editing those same lines from search-everything.php like this did:
if ( $this->options['se_use_tax_search'] )
{
$all_taxonomies = get_object_taxonomies('review');
foreach ($all_taxonomies as $taxonomy)
{
if ($taxonomy == 'post_tag' || $taxonomy == 'category')
continue;
$on[] = "ttax.taxonomy = '".addslashes($taxonomy)."'";
}
}
All I did was change the line:
$all_taxonomies = get_object_taxonomies('post');
to this
$all_taxonomies = get_object_taxonomies('review');
Where 'review' is a registered post-type of mine, and now it searches all of my different post types as well (not sure why). Quite sure this isn't the best way to go about it, but it works for now!