Лучше использовать apt-get для установки lxml (или пакетов python, имеющих расширения c), а затем извлекать чистый пакет python из pypi. Кроме того, я обычно стараюсь избегать использования easy_install для установки верхнего уровня, я скорее создаю виртуальную среду, используя virtualenv, а затем использую easy_install, созданный virtualenv, для поддержания чистоты моих настроек.
Эта стратегия успешно работает для меня для нескольких производственных сред.