I'll go out on a limb and say that the specified key doesn't technically exist, so the error message is technically accurate but doesn't tell the whole story. This should be an easy fix.
S3 buckets have two¹ endpoints, "REST" and "website." They have two different feature sets. The web site endpoint provides magical resolution of index documents (e.g. index.html, which appears to be what is actually supposed to be returned to the browser in the example you provided) while the REST endpoints don't.
When you configure CloudFront in front of a bucket used for web site hosting, you usually don't want to configure the origin as an "S3" origin by selecting the bucket name from the drop-down list; instead, you want to configure it as a "Custom" origin, and use the web site endpoint hostname as provided in the S3 console (e.g. example-bucket.s3-website-us-east-1...) because otherwise, CloudFront assumes you want it to use the REST endpoint for the bucket (which allows authentication and private content, which the web site endpoint doesn't).
Important
Do not select the name of your bucket from the list, for example, example.com.s3.amazonaws.com.
http://docs.aws.amazon.com/gettingstarted/latest/swh/getting-started-create-cfdist.html
The documentation was refactored since this question was originally answered, so the message shown above now appears one page later, and has been reworded, but the gist is the same. The "name of the bucket" seems to refer to the choices shown in the drop-down, which is not what you want.
Note
Be sure to specify the static website hosting endpoint, not the name of the bucket.
http://docs.aws.amazon.com/AmazonS3/latest/dev/website-hosting-cloudfront-walkthrough.html
The hint that you're using the REST endpoint for the bucket is because the error message wouldn't be in XML if you were using the web site endpoint -- the web site endpoint returns error messages in HTML, instead of XML.
Create a new origin for the CloudFront distribution, as described, then change the behavior to send requests to the new origin, then send a CloudFront cache invalidation request for /* and you should be set.
See also:
http://docs.aws.amazon.com/AmazonS3/latest/dev/WebsiteEndpoints.html#WebsiteRestEndpointDiff
¹ two endpoints. Technically, there are more than two, since all buckets have at least two possible REST endpoint hostnames... but there are two types of endpoints. Buckets also have an optional transfer acceleration endpoint that uses the AWS edge network (the same infrastructure that powers CloudFront) for faster/optimized transfers, particularly from geographic locations more distant from the region where the bucket is provisioned, but without using the CloudFront cache. This endpoint looks like https://example-bucket.s3-accelerate.amazonaws.com if you activate it, and carries an additional usage charge for most requests since you are using more of the AWS network and less of the public Internet... but, that is a difference in the behind-the-scenes deployment of the endpoint, not the behavior of the endpoint. The transfer acceleration endpoint is still a REST endpoint, so just like the other REST endpoints, it does not have the web site hosting features. CloudFront won't let you use an acceleration endpoint for an origin domain name, because that wouldn't make sense -- if such a configuration were allowed, requests and responses would loop through the AWS Edge Network twice and increase both latency and costs without providing any benefit.
