Como Hacer funcionar formulario de contacto php?

[jiko_nany]

Estimados tengo el siguiente problema, agradecería mucho de su ayuda.

Necesito habilitar un formulario de contacto común y corriente, super basico, que llegue a mi mail. He visto muchos tutoriales, todos son muy similares. Pero a la hora de implementarlos en mi servidor (que es arrendado, pero si tiene habilitada la función del php para envio de mails) no me funciona. Me gustaría que me digan que estoy haciendo mal o que me falta agregar al proceso. Se los cuento

Tengo el siguiente código para el formulario.php:

Código:

<form method="POST" action="enviar.php">
<table width="300" border="0" cellpadding="0" cellspacing="4">
    <tr>
      <td width="109">Nombre:</td>
      <td width="179" colspan="2"><input name="Nombre" title="Ingrese su Nombre" type="text"  id="Nombre"></td>
    </tr>
    <tr>
      <td>Apellido:</td>
      <td colspan="2"><input name="Apellido"  title="Ingrese Apellido" type="text" id="Apellido"></td>
    </tr>
    <tr>
      <td valign="top">E-mail: </td>
      <td colspan="2"><input name="email" title="Ingrese su E-mail" type="text" id="email2"></td>
    </tr>
    <tr>
      <td valign="top">Telefono:</td>
      <td colspan="2"><input name="fono" title="Ingrese su Telefono de Contacto" type="text" id="fono"></td>
    </tr>
    <tr>
      <td valign="top">Mensaje: </td>
      <td colspan="2" valign="top"><textarea rows="5" title="Ingrese su consulta " class="formu" name="mensaje" cols="25"></textarea></td>
    </tr>
    <tr>
      <td>&nbsp;</td>
      <td><input type="submit" value="Enviar" name="enviar" title="Envie su consulta" class="button"></td>
      <td><input type="reset" value="Borrar" name="borrar" title="Borre este formulario" class="button"></td>
    </tr>
  </table>
    </form>

y en la acción enviar.php tengo esto:

Código:

<?php

//E-mail en donde se recibirá el Formulario.

$recipiente = "[email protected]";

//URL de tu Sitio Web.

$sw = "http://www.nickotina.cl";

//Mensaje que te llegará al Correo, con los datos ingresados.

$msg = "El Sr: $Nombre, envia el formulario con los siguientes datos:\n\n\n\n

Nombre: $Nombre
Apellido: $Apellido
Email:  $email
Fono:  $fono
Mensaje:
$mensaje\n\n";

//Comprobamos que los campos del formulario se encuentren completos.
if (empty($Nombre)){
echo "<p><b><font color=#FF0000>Error:</font> No ha
ingresado su Nombre.</b></font></p>";
}
if (empty($Apellido)){
echo "<p><b><font color=#FF0000>Error:</font> No ha
ingresado su Apellido.</b></font></p>";
}
if(empty($email)){
echo "<p><b><font color=#FF0000>Error:</font> No ha
ingresado su E-mail.</b></font></p>";
}
if(empty($fono)){
echo "<p><b><font color=#FF0000>Error:</font> No ha
ingresado su Telefono.</b></font></p>";
}

if(empty($mensaje)){
echo "<b><font color=#FF0000>Error:</font> No ha
ingresado su Mensaje.</b></font></p>";

}
else{

//Limpiamos de posibles ataques para que no ingresen codigo html .

$mensaje = ereg_replace("\r\n","<br>", $mensaje);

$Nombre = htmlentities($Nombre);
$Apellido = htmlentities($Apellido);
$email = htmlentities($email);
$fono = htmlentities($fono);
$mensaje = htmlentities($mensaje);


mail("$recipiente", "Contacto Web Tu_Nombre", "$msg", "FROM: $email");

echo"Señor/es <b>$Nombre</b>.
<br><b>Pronto Estaremos  en Contacto con Usted.</b><br><br>
<br>
<br>Atte.  tu nombre u empresa
<br>
</p>
<br>
<a href=$sw>http://www.nickotina.cl</a>.</p>";
}
?>

Lo que hago, es subirlos al servidor, llamo la url de "formulario.php" y cuando le doy enviar me sale esto



Por favor, agradecería que me orientaran en esto.. llevo más de tres semanas leyendo e intentando habilitarlo.