AWS aws.push ImportError: No module named boto in Ubuntu
What happened is that the eb command line interface available in that specific AWS tutorial (http://docs.aws.amazon.com/elasticbeanstalk/latest/dg/create_deploy_Ruby_rails.html) does not provide the latest version of boto.
When you did
pip install boto
you installed the latest version from https://github.com/boto/boto which solved the issue.
Make sure when you install Python modules that you look at the output to verify that the install happened properly. On Mac/Linux I had to run sudo to get boto to install properly.
sudo pip install boto
If on OSX w/o pip installed:
sudo easy_install pip
sudo pip install boto