دقیقا اولین query بعد از اتصال به دیتابیس این query باشه فکر می کنم مشکلتون حل بشه
set names "utf8"
یعنی اول query بالا رو اجرا کنید و بعد query خودتون رو . می تونید این خط رو توی فایل کانکشن دیتابیس قرار بدید .
مثلا : mysql_query('set names "utf8"');