Nice Search Plugin

I was using this plugin in my wp 2.0 and it works pretty well but after I change the permalinks of my search page, it’s not working anymore, all searches go into 404 pages but after I tried going back to the old permalinks, it worked again. Any idea what could be done so that it works for the new permalink?

https://txfx.net/code/wordpress/nice-search/

thanks ??