1. После установки соединения с бд установи кодировку
$link->set_charset("utf8");
2. Проверить кодировку mysql должна быть "Кодировка сервера: UTF-8 Unicode (utf8)"
3. Сама таблица должна иметь кодировку "utf8_general_ci".
4. Проверить чтобы все файлы были кодировки utf8
5. Проверить htaccees файл, если такой имеется.