Os documentos estão desatualizados / enganosos.
O !
deve ir antes de --destination
, não depois dele. Experimente:
-A OUTPUT ! --destination 127.0.0.1 -m state --state NEW -j LOG --log-prefix "new_connection " --log-level 7
A pista é a linha de resumo na página de manual :
[!] -d, --destination address[/mask][,...]