If you are getting this error on your android device while connecting to Exchange 2010 or Office 365, it can be easily fixed. When the account is set up correctly on the phone a notification is sent to it. This has to be opened in order for the account to work. Unfortunately the phones hide the notification window or you may have missed the notification.
To get the notification again, try swiping down from the top of the screen to open it. There was a notification which asked me to accept. I clicked on it and after that the mail started syncing. My phone is now syncing just fine and I can send and receive emails from my exchange server. By the way I am using Office 365.