Hmm, have you all got magical powers or something?
I just tried to get an email sent out by creating a new account, and blam it is working again.
It was a php send_mail function, not sure if that has anything to do with it though.
Thanks again for your quick replies.