I also have this issue and have been looking into it for a long time. It seems that there is no such problem on python 3+. The problem is actually on google.protobuf
pip uninstall protobuf
pip uninstall google
pip install google
pip install protobuf
pip install google-cloud
create an __init__.py
in "google" folder.
cd /path/to/your/env/lib/python2.7/site-packages/google
touch __init__.py
Hopefully it will work.