Si sigue sin funcionarte prueba asi, ya que las comillas suelen dar problemas.
Cita: $query = mysql_query("INSERT INTO contactos (nombre,email,mensaje) values ('".$_POST['nombre']."','".$_POST['email']."','".$_POST['mensaje']."')");
lo que e echo es sacar los valores del interior de las comillas. asi '".$variable."'
Un Saludo