AWS S3 "Could not upload test file: Timeout" error

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.