Random User not able to get Iphone to work with Exchange 2010

I have about 25 users with various devices- Androids/Blackberry/IPhone.  I have never had a problem setting anyone up.  Most recently I have had a couple of users with new IPhones not be able to sync.  I can set my account up on either device and it works.  I cannot set them up any device.  I can pick any other random userthat does not have a device and add them to thier devices.  I just can't set theses 2 users up.  I have deleted accounts and recreated.

Thier exchange account shows the manage mobile device option so its sees them but when you open it up  no device actually shows up.  So at some point there is some kind of communication to exchange.

Everyone else works fine and as I said before- I can pick any other random user that does not have an active-sync device and create an account for them on the new device.  I have also tried different various IPhone OS (3.12 and different 4 versions) as well as different type of device (Android).

Anyone seen this?  Have any clues?