Search & Replace Database content

I'm cloning sites in a Multisite scenario using the "New Blog Templates" plugin. That part is working fine. The page slugs contain the text phrase "something-cityname" and the content contains many instances of "CityName".

I'm looking for a way to do a mass search and replace of "-cityname" in the slugs and "CityName" in the content. Attempts at exporting the site tables, doing search and replace in a text editor (NoteTab Pro),dropping the old tables and re-uploading the edited tables result in the theme options and widgets being lost.

Any ideas?