I had some messages from my fail2ban log like this:

 2012-02-03 00:59:33,810 fail2ban.actions.action: ERROR  iptables -N fail2ban-apache
 2012-02-03 00:59:33,838 fail2ban.actions.action: ERROR  iptables -N fail2ban-apache-overflows
 2012-02-03 03:42:49,355 fail2ban.actions.action: ERROR  iptables -D INPUT -p tcp -m multiport --dports http,https -j fail2ban-apache-overflows
 2012-02-03 03:43:04,998 fail2ban.actions.action: ERROR  iptables -N fail2ban-ssh-ddos
 2012-02-03 03:43:05,035 fail2ban.actions.action: ERROR  iptables -N fail2ban-apache-overflows
 2012-02-03 07:13:04,720 fail2ban.actions.action: ERROR  iptables -D INPUT -p tcp -m multiport --dports http,https -j fail2ban-apache-overflows
 2012-02-03 07:13:20,154 fail2ban.actions.action: ERROR  iptables -N fail2ban-ssh-ddos

I read over here about a workaround that goes like this:

Edit /usr/bin/fail2ban-client and add a call to time.sleep to mitigate a race condition:

def __processCmd(self, cmd, showRet = True):
    beautifier = Beautifier()
    for c in cmd:
        time.sleep(0.1)
        beautifier.setInputCmd(c)