Попросите хостера перенести базу, нормальные хостеры переносят и сами сайты с других хостингов + иногда при условиях дают месяц бесплатного хостинга
Ваша проблема известна многим опытным вебмастерам, которые часто переносили сайты с одного хостинга на другой.
Советую вам скачать скрипт с сайта [url]http://sypex.net/[/url], при бэкапе\восстановлении БД - изменяйте кодировки, это можно сделать в коде скрипта. Желаю удачи! Эксперементируйте с кодировками
