I just got an Ubuntu instance on Linode. To secure the SSH on it, I installed fail2ban (using apt-get), but then had a problem: fail2ban kept banning my IP (for limited durations, thankfully) even though I was entering the correct password. So I removed fail2ban and installed denyhosts instead. Same problem, but more severe: It seems like every time I SSH in, my IP gets banned. I remove it from /etc/hosts.deny, restart denyhosts and log in again, and my IP gets banned again.
The only explanation I can think of is that I've been SSH-ing in as root (yes, yes, I know); maybe something is set somewhere that blocks anyone who SSH-es in as root, even if they log in successfully? This seems bizarre to me. Any ideas? (Whitelisting my IP is a temporary fix. I don't want to only be able to log on from one IP.)