Search doesn't work with SEFUs on - redirects to main page

I am upgrading from 1.2.7 to 1.3.7, and everything seems to be working well except the search function. It redirects me to the main page when I have SEFUs turned on:

index.php/main_page/advanced_search_result?main_page=advanced_search_result&search_in_description=1&keyword=bag

That returns no products, just displays the main index page of the store. It looks like it's using a weird combination of mod_rewrite and querystring parameters.

The string below (with SEFUs off) works however, and returns search results:

index.php?main_page=advanced_search_result&search_in_description=1&keyword=bag

Any ideas on how to resolve this? I would like to have SEFUs left on, and like the out-of-the-box solution that Zen Cart now provides... it makes the upgrade path that much easier. Thanks.