problems sending mail from my blog contact form

Hi guys, i have installed Contact Form to my blog on a new host today. it report to have sent the mail but i never get it in my mailbox.

The plugin has options to send mail both using php mail and wp-mail, i’ve tried both options but with no luck. I would be very happy if someone could give me a pointer in the right direction. I do suspect something missing on the host as i had this working locally on my xampp setup.

The url to my site is http;//www.ruudsit.org if someone want to check it out, it’s in norwegian but you just need to click the button labeled “Kontakt meg”