Si está utilizando mysqli , emita este comando justo después de conectarse:
$mysqli->set_charset("utf8");
Esto configurará la codificación de su conexión a UTF8 (igual que usa su tabla).
Con mysql simple , usa esto:
mysql_query("SET NAMES utf8", $conn);
mysql_query("SET CHARACTER SET utf8", $conn);