А что Вы там хотите хранить в UTF8? Но если очень хочется, то создавайте БД так:
CREATE DATABASE `mail` CHARACTER SET utf8 COLLATE utf8_general_ci;
Все остальное - по-прежнему.
Если нужно переделать существующую базу, то можно так (ВНИМАНИЕ! Все что Вы делаете - делаете на свой страх и риск!):
1. Остановить mysql (и postfix, т.к. какое-то короткое время у Вас будет неверный список пользователей и Ваши корреспонденты могут получить "отлуп" по причине отсутствия пользователей).
2. Переименовать существующую директорию Вашей БД, например:
mv /var/lib/mysql/mail /var/lib/mysql/mail_old
3. Запустить mysql.
4. Создать новую БД (войдя, естественно, в mysql)
CREATE DATABASE `mail` CHARACTER SET utf8 COLLATE utf8_general_ci;
use mail;
5. Создать таблицы, как в прежней БД
CREATE TABLE users LIKE mail_old.users;
CREATE TABLE domains LIKE mail_old.domains;
CREATE TABLE transport LIKE mail_old.transport;
CREATE TABLE forwardings LIKE mail_old.forwardings;
6. Для каждой таблицы сделать
INSERT users SELECT * FROM mail_old.users;
INSERT domains SELECT * FROM mail_old.domains;
INSERT transport SELECT * FROM mail_old.transport;
INSERT forwardings SELECT * FROM mail_old.forwardings;
7. Выйти из mysql и запустить postfix.
8. Перед удалением старой БД mail_old проверить работу новой.