I had exactly the same issue last couple of weeks. There is one user with Curve 8520, keeps getting Cannot connect to server.
At first, we thought that the line probably did not activate BES feature, probably just activated BIS, so we tried to activate the user on another BB which confirmed with BES plan on it, failed. Tried to activate myself on the Curve, it works just fine, activation goes smooth without any problem. So data plan issue is not in the list.
Tried removed him from BES, re-add, change with different password, add him into another BES server, closed outlook, with outlook opened, all failed.
At last, we disabled all the rules on his outlook, use the exact email address that shown in BlackBerry Manager,
Example_Example2_Example3@company.com, with all the upper case and lower case, and it gone through the activation. Maybe you can try this.