While attempting to install DenyHosts, I got an error about “invalid Python installation”. I found the solution here.

Basically just:

sudo apt-get install python2.4-dev