Ну давай, попробую помочь чем смогу, раз никто больше не откликнулся.
Во-первых, что значит "бэкап БД"? Чем он сделан? Это текстовый SQL-скрипт (дамп) или просто копия бинарников базы?
Если дамп текстовый (например через PHPMyAdmin, который, кстати, кодировку таки не позволяет выставить, сделанный), то можно попробовать вот что:
Есть в Линухе такая библиотека iconv. Заточена она как раз под перекодировку текста. И есть к ней пользовательская консольная морда с аналогичным названием. Т.е. делаешь так:
[root@localhost]$ iconv -l
Вывалится список доступных кодировок
Дальше:
[root@localhost]$ iconv -f koi8-r -t cp1251 dbbackup.sql > dbbackup_cp1251.sql
Вместо koi подставишь UTF-кодировку. Я не помню просто, как она называется.
P.S. Сам не пробовал, но теоретически

должно сработать.