Exchange 2007 can not send email to the Internet

We are currently in the beginning stages of migrating from Exchange 2003 to Exchange 2007. We have got to the point where internal mail between the two systems is working perfectly with all of our testing accounts, the problem is now that Exchange 2007 is not able to send email to external domains.

Seems like an easy enough problem, I've googled it read many articles that have all said the same thing. Create an Internet Send Connector with an address space of '*' and a cost of '1', use domain name system '(MX)' records to route mail automatically.

After reading through that on so many different sites including technet I finally went ahead and did just that. I sent an email to an external address from one of the testing accounts and it didn't make it. I went and checked the mail queues on the hub server and the Unreachable queue had several hundred other messages in it! All email destined for the Internet from the Exchange 2003 side started trying to get out through the Send Connector which still couldn't send to the internet.

I disabled both the Windows Firewall and the Anti-virus in case one of them was preventing the mail from getting sent, and the Unreachable queue kept growing. I deleted the Send Connector and after a few minutes mail started routing out to the Internet as normal.

There was only two other thing that I thought might be going wrong. I checked using nslookup that the domain were resolvable by the server, and manually connected to the remote SMTP servers from the server using telnet to verify that the connections could be opened, both worked.

The diagnostic tools built into Exchange 2007 told me nothing more than 'A matching connector can not be found' even with the * connector. I'm stumped can anybody help me?