We have quite a few iPhones in the company. All of them have their respective Exchange mailboxes configured. This works great.
There are also a few Android phones. They all work fine too.
I have an Android phone and it never works. I enter the exact same details that I would for everyone else. I am a domain administrator. I recall in past that there is an attribute in AD that you need to change for administrators so they can connect their mailbox to any iPhone/Android. Is this the case?