Good to see this issue is acknowledged. We actually have it and were working with MS support for months to figure it out. In the end because of 3 lines out of the Intune Device logs send to us by support we figured it out. Intune was actually taking the Display Name and using that as Common Name in the certificate request.
This can fail early in the process if the Display Name has special characters in it. Or it succeeds and provides the certificate with a Common Name value that is wrong. (In our case the Display Name) Then when using the certificate for connecting to for example Wifi it will fail the authentication.
Workaround for us was to use the exact same value for the Display Name and Common Name. But this is only feasible for some testing.
Intune_Support_Team What would have been helpful in finding this issue must quicker is to have access to the Intune Device logs. As a customer I noticed straight away that the common name value used in the certificate request was wrong. But this error message only showed up in the Device logs.