This is a weird one, but I couldn't import google.protobuf for a while because the PyPI installation didn't include an init.py file in the top-level google directory. Doing a reinstall produced the same results; the top-level google directory still lacked an init.py file.

By looking at this repo, I would expect to see it there. Perhaps you're doing something in the setup.py that is stripping it out unintentionally?