Symptoms
You are trying to validate your new S3 destination, but receive the above error.
Description
If you are using Amazon as your S3 backup make sure to use Amazon S3 type, not S3 Compatible when creating the remote destination.
Workaround
Make sure to use the correct backup type. Amazon S3 when your bucket is at Amazon and S3 Compatible when the remote destination is not at AWS.