It looks like you're new here. If you want to get involved, click one of these buttons!
Turns out that the CNAME that you need to apply to your domain to allow Amazon to sign your emails uses something like this:
**************._domainkey.your_domain.com (where ******** is some random text).
Unfortunately, older versions of Plesk will not allow you to enter the '_' (underscore) character - the reason is just plain boring, so I won't explain.
However, if you have access to the database which is running Plesk - the PSA as it is known, then you have a work around:
This worked for me and Amazon took about 30 seconds to auth my domain once I had carried out the instructions contained in that article.
Thanks Nathan, I'm sure users who uses an old version of Plesk will find this useful.