Subito dopo la connessione al database hai fatto questa query?

mysql_query("SET NAMES 'utf8'");