Our organization has been battling this since November of last year - our new IOS devices would not enroll in Intune MDM using Apple Configurator 2. Started with Apple of course, and they could not figure it out, essentially gave up and and said all I could do was pay for an engineering consulting engagement (starting at $800 per incident). Seriously? Totally unimpressed with Apple - they would not even look at the log files being generated by the iPad that clearly showed it was a connection issue caused by an untrusted certificate.
Opened a Microsoft ticket and provided them the iPad log file. Took a few weeks and escalation but they figured it out and provided me this link and walked me through the workaround. Someone at Microsoft needs to send this information over to Apple support.