O que o Celso recomendou deve servir bem.
Caso contrário (e até acho mais simples), entra no phpmyadmin, exporta a base de dados e guarda um backup, abre no notepad++ uma segunda cópia, faz o search / replace, e carrega-a novamente após apagares as tabelas que estão online (não apagues a base de dados).
Isto deverá ser mais eficiente desde que a base de dados não seja gigantesca em termos de MB.