Se stai usando mysqli , emetti questo comando subito dopo la connessione:
$mysqli->set_charset("utf8");
Questo imposterà la codifica della tua connessione su UTF8 (come usa la tua tabella).
Con semplice mysql , usa questo:
mysql_query("SET NAMES utf8", $conn);
mysql_query("SET CHARACTER SET utf8", $conn);