Isso foi falado antes em SF. iptables
mudou a maneira de aceitar parâmetros. Agora o estrondo deve ser antes do parâmetro, para que suas linhas se tornem assim:
-A INPUT -p tcp --dport 22 ! -s 10.0.0.0/8 -m state --state NEW -m recent --set --name SSH
-A INPUT -p tcp --dport 22 ! -s 10.0.0.0/8 -m state --state NEW -m recent --update --seconds 600 --hitcount 25 --rttl --name SSH -j DROP
E sim, todo blog na internet está errado.
(Esta é uma cópia da minha resposta no StackOverflow, o problema é essencialmente o mesmo)