Hmm... also wenn du alles in der functions.lib.php richtig hast, dann fällt mir nur ein, dass dein Webspace die Funktion mail nicht unterstützt. Frag doch einfach bei denen nach.
Ansonsten gibt es da eine Liste von E-Mail-Anbietern, bei denen es dann nicht geht. Versuch es mal mit marsmail.de