Try replacing search-and-replace.php with the file contained here: Test Version of Search & Replace. Please let me know how it works for you.
Ok, the plugin author (Frank) will be away for a month, so I tried to fork the plugin, but there’s 116 plugins waiting review.
You can download the new plugin directly from my site for now. Please let me know if it works for you.
The fixes from RonG are now inside the new version. THANKS to RonG