Search and taxonomies not talking?

I have set up a site (creaturez.org), and have successfully created a custom taxonomy (using the more taxonomies plugin here: http://labs.dagensskiva.com/plugins/more-taxonomies/), and have successfully displayed it on my site for searching using the taxonomy_picker plugin (http://www.squidoo.com/taxonomy-picker-wordpress-plugin).

All is well except that the search is not working. No matter which search parameters I enter, either through the regular wordpress text search or using my taxonomy dropdowns, the site either returns all posts or no posts.

Am I missing something essential that allows the search function to talk to the taxonomy?

Thanks.