No uses los acentos en el asunto. Te ahorrarás problemas y además no es nada recomendable (
http://www.netiqueta.org/netiqueta_correo.shtml).
No sé si habrá algo mejor, pero con:
string
ereg_replace ( string pattern, string replacement, string string )
Podrías cambiar el asunto antes de mandarlo.
Espero que te sirva ;)