Usually this problem is caused by your cel service provider. Verify you have the Blackberry Enterprise plan and not the Blackberry Internet plan. You will have to change plans and then have them send you new service books. Best bet is to delete all the old service books and have them send you the new ones.
Also verify you have tcp port 3101 and 3500 open on your firewall
Give those a try and post back. thanks