tombs, let us know if the prebuilt doesn't work for you, and I'll try to help you build from source.
Basically I followed the directions Kovid posted here:
http://calibre-ebook.com/download_linux
and used apt-get to install latest available repository version of everything on the list of dependencies. After that, it was an iterative process of executing 'sudo python setup.py install', guessing from the error messages returned by make what dependencies remained to be installed, and trying again once I had added the needed libraries.
The only dependency I had to build from source was ICU, because the version in the repository was too out of date. I got the ICU code here:
http://site.icu-project.org/download/49