Да.. похоже я неправильно понял тему. DNAT работает правильно, но вам, судя по всему нужно не это

В общем, чтобы сделать прозрачное проксирование, прокси сервер и шлюз у вас должны располагаться на одной машине. Тогда как раз и получится прием с -j REDIRECT.
Cудя по всему, у вас именно так все и есть, поэтому правило
Код:

iptables -t nat -A PREROUTING -p tcp --dport 80 -j REDIRECT --to-ports 8080
должно работать.