Zde může být chyba v nastavení připojení MySQL. Tento příkaz MySQL spusťte, když se připojujete k databázi z PHP, než spustíte jakékoli jiné příkazy SQL:
SET names 'utf8';
Tím by se mělo nastavit kódování připojení na UTF-8. Jak říkáte, stránka a databáze jsou již v UTF-8 (to by také mělo znamenat, že stránka odesílá Content-Type: text/html; charset=utf-8
); samotné připojení může mít omylem ve výchozím nastavení jiné kódování :(