Si estás usando la función de mail, debes indicar en que encode vas a enviar la información. Eso se logra en el cuarto parametro de la función mail. Indica que vas a enviar UTF8. Mira el cuarto ejemplo del
manual de PHP para que entiendas lo que te quiero indicar. Pero en vez de indicar iso-8859-1 indica utf8.