I've added the correct CNAMEs to my DNS, but I can still not add the DKIM config:
PS C:\WINDOWS\system32> New-DkimSigningConfig –DomainName domain.com –Enabled $true
Creating a new session for implicit remoting of "New-DkimSigningConfig" command...
Error publishing public key TXT record. Config was not created. Please try again.
The reason I'm doing this is because Exchange admin center says "No DKIM keys saved for this domain." in the DKIM configuration for this domain.