I have added a domainkey for my domain. I checked on  http://mxtoolbox.com/dkim.aspx and  http://dkimcore.org/tools/keycheck.html. They exist and are displayed properly. Yet when I click on verify, it says "Verification Failed"

Can you please look into it?

Thanks