Another difference between Fail2ban and Denyhosts is that Denyhosts can share the block list with other Denyhosts users. With Fail2ban, you can only block IPs that your server has seen before - with Denyhosts, a brute-force attempt may never even get to your server, if somebody else has seen it, and the block list is downloaded to your server before the attacker gets to your computer.
Yet another difference is that Fail2ban uses iptables, while Denyhosts uses tcpwrappers. Others have mentioned this difference before, but there are a couple of side notes worth mentioning.
iptables is limited in how many IP addresses you can block efficiently. That's probably one of the reasons why Fail2ban doesn't have a mechanism to share block lists.
Another effect is that when iptables is replaced with nftables, Fail2ban will probably stop working or needs to be rewritten. Denyhosts will likely continue working.
So, both have advantages and drawbacks. I like both; for myself, I'm using Denyhosts because usually I only want to protect SSH, and I like sharing the block list.