Ustawienia połączenia MySQL mogą być tutaj winne. Uruchom to polecenie MySQL, gdy łączysz się z bazą danych z PHP, przed uruchomieniem innych poleceń SQL:
SET names 'utf8';
Powinno to ustawić kodowanie połączenia na UTF-8. Jak mówisz, strona i baza danych są już w UTF-8 (powinno to również oznaczać, że strona wysyła Content-Type: text/html; charset=utf-8
); samo połączenie może przypadkowo mieć domyślnie inne kodowanie :(