If this is not a new device in your environment, I would check the troubleshooting log for any clues. If nothing out of the ordinary, I would delete the device's record from the console. Other ideas for new and existing devices:
a) Check the time on the phone. I had a user that liked to manually set the time 10 minute (+/-) of the real time. Make sure it is set to Automatic Date and Time.
b) Go to Groups and Settings -> Dev & Users -> General -> Enrollment and check
--> Check for enrollment restrictions at the current OG and/or above OG
--> Check also in the Terms of Use rules
c) Try to enroll the device by Server Details, not by Email Address.
d) For your On-Premise environments, are all of your certs current?
e) Turn off Wi-Fi on the device
f) We have a Shared Saas with AW Cloud Connector, in the ACC server I can see the Logs. Can you see your IIS logs?
It is not authentication since you've made it pass that.
Hope this helps.