Errors when trying to send e-mail when using Ubercart
So after much searching I came across this post:

http://shutterfreak.net/blogs/olivier-biot/2010-06-24/configuring-smtp-server-sending-mail-drupal

Apparently issues with the default SMTP are quite common. This post explains how to install and configure "SMTP Authentication Support module" and PHPmailer to basically override the default.

Worked great for me.