This just started happening this afternoon, Exchange was setup Friday evening, was working fine up until this afternoon, it just stopped sending outside emails. very strange.
Open a Command Prompt on the Server and attempt to Telnet to TCP Port 25 on a couple of other mail servers. You'll have to look up the MX records for a few mail servers:
"Telnet mx3.hotmail.com 25"
"Telnet mail3.foxnews.com 25"
You should see a response from their mail servers. Both of the above servers are responding to my requests tonight. If you can't connect, then there's probably an outgoing firewall in place. Do you have a Home or Business Internet account? If Home, then maybe your ISP is now blocking outgoing TCP Port 25 connections. Cox blocked outbound requests to non-Cox mail servers years ago (on Cox Home accounts).
If outgoing TCP Port 25 isn't being blocked, then it's time to look at the Exchange Queue and the Message Tracking tool in ESM.