Have you checked to make sure that there is a send connector in place? If not, then you will have to create a send connector. Send connectors create a logical connection to remote e-mail systems. In EMS, go to Org. Config -> Hub Transport -> Send Connectors, and see if you have at least one (Should say Global Internet Connector for Exchange 2010).
If nothing is there, create one:
http://www.petri.co.il/configuring-exchange-2007-send-external-email.htmIf you already have one, then check the Toolbox -> Mail Flow Troubleshooter for more clues about what's going on.