Solution 1:

I've figured it out and I feel a little bit silly for not picking this up sooner.

So for anyone that uses AWS::CloudFormation::Authentication path, the solution of course is:

Make sure your BUCKET policy allows your aws-elasticbeanstalk-ec2-role. DOH!!

It should look something like this:

{
    "Id": "Policy1111Blah",
    "Version": "2012-10-17",
    "Statement": [
        {
            "Sid": "Stmt1440Blah",
            "Action": [
                "s3:GetObject"
            ],
            "Effect": "Allow",
            "Resource": "arn:aws:s3:::my-bucket/*",
            "Principal": {
                "AWS": [
                    "arn:aws:iam::11111111111:role/aws-elasticbeanstalk-ec2-role"
                ]
            }
        }
    ]
}

You can grab the ARN from IAM console.

The instructions in your .ebextensions config files only tell the EB deploy tools what to use to authenticate, but your source bucket (if private obviously) needs to allow that principal access!!!