Hola Chininino
Puede ser tantas cosas:
1.- Que lo estás probando en local.
2.- Que los código están mal escritos.
3.- Si está en el servidor éste no da soporte al PHP.
4.- Que el servidor no tenga habilitado el envío de correos.
Aquí tienes varios videos tutoriales:
http://www.google.com/#q=formularios...247f89db471ef3
Espero haberte sido de ayuda.