Как перекодировать базу данных?

ну просто с помощью Akelpad можно.

нет, не естественно.
BOM — это указание редакторам (заметьте, не операционке), что используется вполне определённая кодировка.
в базе данных нет такой ереси, как bom.
ошибки с кодировками могут возникать, но ситуаций множество:
— кодировка базы данных;
— кодировка файлов;
— кодировка, указанная в html-файле (с помощью meta);
— кодировка, отдаваемая клиенту (браузеру);
— кодировка соединения с базой.
если хоть одна из этих кодировок отлична от остальных, на клиенте может показывать всё, что угодно. если пишете в utf-8, извольте соблюдать несколько простых правил:
1. все файлы должны быть в utf-8 (никаких bom!);
2. базы данных, желательно, иметь в utf-8 (для баз неприменимо понятие bom);
3. после коннекта к базе нужно установить соответствующую кодировку (в вашем случае требуется выполнить запрос SET NAMES 'utf8');
4. браузеру требуется отправить заголовок header('Content-Type:text/html; charset=utf-8');
5. в отдаваемом html должна быть строка <meta http-equiv="content-type" content="text/html; charset=utf-8">