SMTP Issues with Covad

Has anyone had to configure an SBS server for Covad? I have an issue and not sure what to do about it. Currently I have setup our server to send using smtp.covadmail.net with our username and password. It worked before. Now we installed a new firewall and the smtp stopped working and started giving us relaying denied errors. So I put the settings back and reverted everything back. Not able to send still. Contacted Covad multiple times and they have been no help stating they do not permit end users to have their own Exchange systems. If anyone knows a trick I would appreciate it.