Comment 56 for bug 207723

It sounds like voodoo but Timothy's work around did indeed fix the problem for me, probably only temporarily though.
https://bugs.launchpad.net/ubuntu/+source/evolution-exchange/+bug/207723/comments/37

In summary, and assuming your setup worked and then mysteriously stopped working:
1. Delete your mailbox name from the Exchange
2. Authenticate