Po połączeniu z bażą (mysql_connect() mysql_select_db()) daj zapytanie
mysql_query("SET NAMES utf8"); [/code]
Wiem ze niektóre serwery mają domyślnie ustawione inne kodowanie, być może zależy to od kodowania domyślnego tabel czt całej bazy, przez to może się krzaczyć.