I am assuming you are using Office 365. Try the below steps.
Run: New-DkimSigningConfig -DomainName <domain> -Enabled $false before updating the CNAME records.
So here are the steps that you need to complete in order to get this working:
New-DkimSigningConfig -DomainName <domain> -Enabled $false
Get-DkimSigningConfig -Identity <domain> | Format-List Selector1CNAME, Selector2CNAME
Grab the CNAMES and update them in DNS.
Then run the command:
Set-DkimSigningConfig -Identity <domain> -Enabled $true