Algunos servidores de alojamiento (sin nombre y sin comentario) restringen muchas veces al cliente, esto hace que la función mail de WordPress no funcione a la primera y necesites otro recurso que afortunadamente existe

El plugin en cuestion es wp-mail-smtp.0.8.6 muy fácil de configurar y cuya explicación en inglés no tiene muchas dificultades, tambien existe alguna que otra documentación en español y de hecho resolverá el problema del envío de correo en WordPress.

En el sitio del autor nos da un ejemplo de configuración de como poder echarlo a andar si tienes dominio en Google Apps y lo traduzco a continuación.

Gmail / Google Apps

Para enviar correo a traves de Gmail o Google Apps, utilice la siguiente configuración:

Mailer: SMTP
SMTP Host: smtp.gmail.com
SMTP Port: 465
Encryption: SSL
Authentication: Yes
Username: usuario@gmail.com
Password: su contraseña

Puedes descargar wp-mail-smtp.0.8.6 en WordPress.org