Ubuntu – Failing to send email on Ubuntu box (Karmic Koala)

I have a home network with an XP and Ubuntu (9.10) box. I have created a small test php script for checking that I can send emails from my machine. I am using the same php.ini file with the same [mail settings], yet the file works on my XP box, and fails on the Ubuntu box. I have included the script here, hopefully, someone can spot whats going wrong:

<?php

// send e-mail to ...
$to="myemail@hotmail.com";

// Your subject
$subject="Test Email";

// From
//$header="from: test script";
$header='From: host-email-username@hostdomain_here' . "\r\n" .

// Your message
$message="Hello \r\n";
$message.="This is test\r\n";
$message.="Test again ";

// send email
$sentmail = mail($to,$subject,$message,$header);

// if your email succesfully sent
if($sentmail){
echo "Email Has Been Sent .";
}
else {
echo "Cannot Send Email ";
}
?>

The emails have been spoofed for obvious reasons, but otherwise, the script is exactly as the one I tested

[Edit]
I have since installed mailutils package on my Ubuntu box, now the script runs and returns 'Email has been sent'. However, the mail never arrives in my mail inbox (I've waited 1 day so far). Is there something else I need to be looking at?