I had this issue and realised that whilst I did have libxml2 installed, I didn't have the necessary development libraries required by the python package. Installing them solved the problem:
sudo apt-get install libxml2-dev libxslt1-dev
sudo pip install lxml