The process you describe seems correct, however, it’s important to have in mind some timing related considerations.
In particular, after you setup the CNAME value in your DNS it will take some time for DNS to propagate it and it will also take some time for the verification process to notice it’s their so first question would be how long did you wait after adding the record to your DNS provider to decide it was not working?
It would also be important to note how much time had passed since the customer domain was created (you’re given the verification data) and you actually added the verification data to your DNS provider. For example, if you create the custom domain today, but only add the DNS entry the day after in some cases it may take up to a few hours for verification to detect the entry.
On the other hand, if you create the domain in Auth0 and immediately update the DNS the verification process should be fairly quick, as in, verified within the next few minutes.
Having said all of that, there may be some other considerations and/or an actual issue preventing your verification. It’s hard to say without sharing the concrete information so given you can configure custom domains your subscription should also allow you to submit private support tickets which may be a better option for this case if you haven’t done so already.