I'd start by checking the send connector. Open Exchange Management Console then expand Organization Configuration -> Hub transport. Click the Send Connectors tab and check that you have a send connector present and it is enabled.
Let us know how you get on
