Denyhosts and fail2ban fulfill the same purpose; they just do it in different ways.
As noted, denyhosts uses the hosts.deny file to lock out IP addresses. In order for this to work, your sshd must use tcpwrappers. This is accomplished by either being called from xinetd (uncommon), or by the tcpwrapper libraries being compiled into sshd. You can check for the former by (most likely) looking for a relevant file in /etc/xinetd.d/, or for the latter this way:
Code:
$ ldd /usr/sbin/sshd | grep wrap
libwrap.so.0 => /lib/libwrap.so.0 (0xb7ee2000)
If you don't get any output from this command, then sshd hasn't been built against the tcpwrapper libraries and denyhosts will only benefit you if sshd is called from xinetd.
In contrast, fail2ban inserts rules directly into the firewall. This is good in that ssh won't even see connection attempts from hosts that trip the rules. If you already use a system to manage firewall rules (like firestarter, guarddog, or Ubuntu's ufw) then fail2ban's default monkeying with the raw firewall rules may cause problems. It can be customized to use your preferred firewall system instead, but you may find it easier to simply use denyhosts in such a case.
I don't have a strong preference for one or the other - they each have their strengths in different environments. I would very much recommend setting "PermitRootLogin no" or "PermitRootLogin without-password" in your sshd_config.
Edit: you can always use Linode's web console if you end up locking yourself out like
condate...