After following the advice of others and directions of many from resetting network settings, to deleting phones from the web mail, etc, we discovered on our own something that might help everyone.
We discovered this by connecting one of the new iPhone 6 users to their account and when observing the logs, we found Event IDs 1008 popping up (Event>WindowsLogs>Applications). Analyzing one of the Event 1008 logs, we found that an entry like this “Security settings couldn't be applied to the user device container 'CN=ExchangeActiveSyncDevices, CN=………..”. It was the “CN=ExchangeActiveSyncDevices” that we were most interested in and began investigating that.
The first step was to obviously looked in the Active Directory and when it wasn’t there the next obvious step was to look in the ADSI Edit. We opened ADSI Edit and did a search for “ExchangeActiveSyncDevices” founding a bunch of people who had this container. We navigated to one of the users in ADSI (Edit>Default Naming Context>Users>John Doe) and found the ExchangeActiveSyncDevices container with their mobile devices. What was strange was that we had deleted the devices in the Exchange 2010 Manager (Right click on the user name and select “Manage Mobile Phone”) or via the user web mail (Options>See All Options>Phone). Taking the chance of seeing if this worked, we deleted the ExchangeActiveSyncDevices container and VOILA!…the phone began synching. We tested this theory on several other users and they all worked flawlessly.
The steps we would recommend would be to delete the phones from the Exchange Manager first then go into the ADSI Edit and delete the container there next.
Hope this helps everyone and let us know.