It's been a while since I posted this but it does work now. Sorry I didn't update this thread.
I believe it had something to do with the mail server. If memory serves the server didn't allow us to send email outside the domain anonymously. So if you're having problems, you should check that the permissions are set up correctly on the mail server.
Hope this helps!