I had the same problem (can not install) and was a bit confused, since it was my first attempt at Calibre (at the time it was 0.4.85).
It was pretty obvious that Calibre is the tool to go with so I have reverted to 0.4.83 by
sudo easy_install --upgrade calibre==0.4.83
After searching I found this thread - and the resolution: I have upgraded to the Intrepid packages on Hardy.
I needed to get only the Intrepid packages for python-lxml and libxml2:
and Calibre could be installed:
sudo dpkg -i python-lxml_2.1.1-1_i386.deb libxml2_2.6.32.dfsg-4ubuntu1_i386.deb
sudo easy_install --upgrade calibre
It was the current version: calibre-0.4.89-py2.5-linux-i686.egg that was installed!