While installing Powerline on MacOS X following the documentation, there are some import problems.

It turns out that running python setup.py install installs everything into /path/to/site-packages/Powerline-beta-py2.7.egg/. This folder should be named powerline instead.

Symlinking the included powerline folder to site-packages/powerline seems to fix this.