I had no problems when I set mine up. It might be an issue with your server, especially if you are on hosted exchange.
On a side note, everyone should switch to Google email servers. I just switched my company to Google and cut our email costs by ~70%. The switch was a breeze, and Google is awesome as always.