Sign up for Office 365
Learn more about Office 365
Usually when we see problems like this is has to do with the software on the phone that's either using an out of date ActiveSync application or is just having issues with the version it is allowed to use.
Try using your ActiveSync options in the Exchange Control Panel to set your default ActiveSync policy so it always requires a device with a password, and then try connecting the devices again.
Also, could you tell me the specific way in which you're configuring the ActiveSync profile?