Te recomiendo que uses la libreria phpmailer() ya que aunque se haga funcionar la funcion mail() a la que lleves un par de correos enviados seguro te llegaran a la bandeja de spam.
Utiliza la libreria phpmailer que es mas sencillo, puedes utilizar smtp con encriptacion tls o ssl y todo mas claro y aparte un debug.
Aqui te dejo un poco de informacion sobre dicha libreria:
http://blog.unijimpe.net/enviar-email-con-php-y-gmail/ http://guiabreve.com/enviar-correos-con-phpmailer.html
Saludos!