Na primeira olhada em http://www.nicknettleton.com/ zine/php/php-utf-8-cheatsheet Eu acho que uma coisa importante está faltando (talvez eu tenha esquecido isso). Dependendo da sua instalação e/ou configuração do MySQL você tem que definir a codificação de conexão para que o MySQL saiba qual codificação você está esperando no lado do cliente (ou seja, o cliente lado da conexão MySQL, que deve ser seu script PHP). Você pode fazer isso emitindo manualmente um
SET NAMES utf8
consulta antes de qualquer outra consulta que você enviar ao servidor MySQL.
Se você estiver usando o PDO no lado do PHP, você pode configurar a conexão para emitir automaticamente esta consulta em cada (re)conexão usando
$db=new PDO($dsn, $user, $pass);
$db->setAttribute(PDO::MYSQL_ATTR_INIT_COMMAND, "SET NAMES utf8");
ao inicializar sua conexão db.
