Si ya tienes tu DB en utf8 entonces es problema del charset default de MySQL, ejecuta esta QUERY, justo después de conectar (mysql_connect) y seleccionar tu DB (mysql_select_db):
Con eso ya no debería hacerte falta usar las funciones utf8_encode/utf8_decode