I found that my OSX comes with python 2.6 (which doesn't have check_output) and it was conflicting with python 2.7 that I've installed for EB CLI.
To solve this, I just made .git/AWSDevTools/aws.elasticbeanstalk.push use python 2.7, in its first line:
#!/usr/bin/env python2.7
Also for more insights about S3 and other AWS skills, visit the AWS Course page.