I have tried everything from sitting side by side with my friend that has a blackberry trying to simply get him on my contacts list to message to restarting my phone and all the networks, and I still cannot even get him added as a contact. I know that we have the correct PIN and everything. Any suggestions?
I had the same problem, I found that I had a restriction on my outlook mailbox size. I also found that by going into your mailbox menu and hitting the reconcile now option that it solved this problem. It seems that it only happens the first time and from there on it works fine.