It was still not working with multipart upload disabled. After some more debugging and looking into the S3 access logs I found the request which was failing was for fetching the Bucket Location (http://docs.aws.amazon.com/AmazonS3/latest/API/RESTBucketGETlocation.html)
I had set all permissions for that bucket but needed to add the following to my bucket policy:
{
"Sid": "RequiredByS3Console",
"Action": ["s3:GetBucketLocation"],
"Effect": "Allow",
"Resource": ["arn:aws:s3:::*"]
}