As configurações de conexão do MySQL podem estar com falha aqui. Execute este comando MySQL ao se conectar ao banco de dados do PHP, antes de executar qualquer outro comando SQL:
SET names 'utf8';
Isso deve definir a codificação da conexão para UTF-8. Como você está dizendo, a página e o banco de dados já estão em UTF-8 (isso também deve significar que a página envia
Content-Type: text/html; charset=utf-8 ); a própria conexão pode acidentalmente ter uma codificação diferente por padrão :( 
