We had a similar problem here and it turned out to be a config problem with our router (Cisco). The config of the router was pointing to a firewall that no longer existed.

Our network admin swore up and down that the BES was not going through a firewall - and it wasn't, but when they removed the firewall they didn't update the router settings.