pues yo diria que es un problema de tu server y mas si dices que antes funcionaba,
no se, pero yo probaria la clase phpmailler, se por post de este foro que da muchos menos problemas
http://phpmailer.sourceforge.net/
aqui la puedes descargar y es muy facil de usar
a ver si te sirve
un saludo