Thanks guys.
We have been using pop/smtp for the last week with no problems (using the main account that UBB uses). The mail servers are still mail.ourdomain.com - we just pointed the A record to the new server. I've tried leaving the UBB mail field blank, changed it to localhost and changed it to mail.ourdomain.com with no luck. As you suggested its probably a server issue but I thought I would post back here. I'll post back again and tell you what we figure out in the event it might help someone else.
Thanks!