Mail funktion virker ikke

Hej
Jeg har lavet en side hvor jeg har en kontaktformular lavet vha. mail() funktionen i php. Formularen fungerede fint på webhotellet hvor siden var placeret før den blev officiel, men efter jeg har lagt den op på det nye, virker den ikke mere.
På det nye webhotel skriver de noget man skal være opmærksomme på: www.uni-c.dk/produkter/hosting/webhotel/vejledninger/php/index.html

og jeg mener jeg har opfyldt de krav

-----min kode-----

$navn = stripslashes($navn);
$email = stripslashes($email);
$besked = stripslashes($besked);
$emne = stripslashes($emne);

if($navn == ""){
echo "Du har glemt at udfylde dit navn<br><br><br><a href='java script:history.go(-1)'>Tilbage</a>";
exit;
}
if (!$email || !eregi("^[_\.0-9a-z-]+@([0-9a-z][0-9a-z-]+\.)+[a-z]{2,3}$", $email))
            {
            echo "E-mailadressen er ikke gyldig eller du har ikke indtastet nogen<br><br><a href='java script:history.go(-1)'>Tilbage</a>";
            exit;
            }
if($besked == ""){
echo "Du har glemt at skrive indhold i beskeden<br><br><a href='java script:history.go(-1)'>Tilbage</a>";
exit;
}
if($emne == ""){
echo "Du har glemt at skrive et emne på beskeden<br><br><a href='java script:history.go(-1)'>Tilbage</a>";
exit;
}
else {
$fra="kontaktformular fra hjemmesiden";
if (mail("min@email.com", "$emne", "Besked:\n$besked\n\nE-mail sendt fra $navn, $email", "From:$fra\n Reply-To: $email"))
echo "Vi har modtaget din mail og svarer snarest muligt";
else echo "Mailen blev desværre ikke sendt denne gang, prøv igen senere";
    }

-----Slut på kode-----


Jeg ender hele tiden med "Mailen blev desværre ikke sendt denne gang..."

Er der nogen af jer eksperter der kan hjælpe!