Note that the Python protobuf package and the Google AppEngine both use the root module name 'google' so if one package is installed, the other package can't be located.

For instance protobuf on my mac is installed to (same problem on Linux as well):
/Library/Python/2.7/site-packages/google/protobuf

This will cause the AppEngine SDK imports to fail:
Traceback (most recent call last):
File "/xxx/yyy.py", line 16, in
from google.appengine.api import users
ImportError: No module named appengine.api

Uninstalling the protobuf library fixes the issue.

For now, I am manually removing the protobuf library from my PYTHON_PATH.

It's not really a bug related to protobuf or appengine, they just have conflicting module names that don't play nicely together so I wanted to bring it to the teams attention.