Típico problema de codificación de carácteres, el cual no es tna sencillo de solucionar, sobre todo que esto puede pasar tanto en el asunto como el en cuerpo.
Mi recomendación es que uses la librería PHPMailer para enviar correos:
#
http://phpmailer.sourceforge.net/
Un saludo