On Mac OS X El Capitan I had to run these two commands to fix this error:
xcode-select --install
pip install lxml
Which ended up installing lxml-3.5.0
When you run the xcode-select command you may have to sign a EULA (so have an X-Term handy for the UI if you're doing this on a headless machine).