Зачем хостера менять? Не хостера, а кодировку попробуйте сменить.
И, если не поможет, переведите файлы скрипта из WIN в UNIX формат. Для этого вам в распоряжение редактор AkelPad. Уверен проблема растворится.
А если не растворится - есть же у вашего хостера, наверное, служба поддержки..
И вот ещё, я так смотрю у вас в базе данных fotobase.dat кирилизованные символы заменены, поэтому, есть смысл ещё обратить внимание (и наверное в первую очередь) на то какими программами вы сливаете скрипт на сервер... В общем, если внимательно и аккуратно, то беда ваша лечится за 3 минуты.