For those who use iPhone, with iOS 4 to connect to Exchange Online, you must install an update.

If you don’t install it, you will not be able to connect anymore to Exchange Online. This doesn’t apply to iOS 3.

You can download the update from here http://support.apple.com/kb/DL1061