Last night I found Portsentry that will notice port scans and will block future accesses from those hosts. I followed these instructions to install Portsentry 1.2, and it went very well. The only problems that I had was I had to remove an extra newline in portsentry.c when the compile failed, and the sample init script has an extra '<' character in it.
After I installed it, I wanted to test this out to make sure that it was working, so from my home machine, I ran nmap against it. This recognized the port scan, and blocked it with iptables. I knew that if I restarted iptables, the rule would be wiped out. But when I tried that, I still couldn't ssh into the machine. It took me a while, but I realized that Portsentry added an entry to hosts.deny. Once I removed that entry, everything worked fine again.