CRM For Outlook - Error connecting to Amazon S3

While setting up the Amazon S3 Setup connection, you can see a red button but no description of the error.

The red color means it cannot perform the necessary connection to Amazon S3. It's just a test, but it's almost certain this means it's not going to work for real as well although you should test it if everything seems correct. It's hard to give a more exact error since we don't get a good error message back from Amazon, but here is the list of probable options:

1) Wrong Access Key or Secret Key. Could be a simple copy/paste problem. Did it add a space at the end, did it cut off a character? This should be double-checked.
2) Was the user created with the correct permissions. Specifically was it given "AmazonS3FullAccess" permission: