This is one of the questions of the FAQs of DenyHosts and you can find it here.
To save you a click, the relevant section of the page says, as of Jan 21, 2010:
If you have been accidentally locked out of one of your hosts (because DenyHosts has added it to /etc/hosts.deny you may have noticed that simply removing it from /etc/hosts.deny does not in itself correct the issue) since DenyHosts keeps track of the attempts in the WORK_DIR (/var/lib/denyhosts by default) files. In order to cleanse the address you will need to do the following:

  1.  Stop DenyHosts (”sudo /etc/init.d/denyhosts stop”)
  2.  Remove the IP address from /etc/hosts.deny
  3.  Edit WORK_DIR/hosts and remove the lines containing the IP address. Save the file.
  4.  Edit WORK_DIR/hosts-restricted and remove the lines containing the IP address. Save the file.
  5.  Edit WORK_DIR/hosts-root and remove the lines containing the IP address. Save the file.
  6.  Edit WORK_DIR/hosts-valid and remove the lines containing the IP address. Save the file.
  7.  Edit WORK_DIR/users-hosts and remove the lines containing the IP address. Save the file.
  8.  (optional) Consider adding the IP address to ”’WORK_DIR/allowed-hosts”’
  9.  Start DenyHosts (”sudo /etc/init.d/denyhosts start”)

Note: Not all of the WORK_DIR files will contain the IP address so you may want to use grep to determine which files contain the IP address.
Here is a list of commands for copy-paste:

  1. sudo /etc/init.d/denyhosts stop
  2. sudo vim /etc/hosts.deny
  3. sudo vim /var/lib/denyhosts/hosts
  4. sudo vim /var/lib/denyhosts/hosts-restricted
  5. sudo vim /var/lib/denyhosts/hosts-root
  6. sudo vim /var/lib/denyhosts/hosts-valid
  7. sudo vim /var/lib/denyhosts/users-hosts
  8. (optional)
    sudo vim /var/lib/denyhosts/allowed-hosts
  9. sudo /etc/init.d/denyhosts start