read the docs - especially BESadmins install thread above.. http://www.blackberryforums.com/bes-...es-thread.html
Things to check
1) Firewall port
3) that the damned carrier has correctly provisiioned the device on the enterprise plan (fixes 30-40% of all BB Problems)
For the first device on a new bes I'd cable the device via USB and activate that way. this enables you to be sure bes is working ok, without worrying about EA issues that could be caused by anti-spam etc..