Deve ser apenas:
sudo iptables -t nat -D PREROUTING -p tcp --dport 80 -j REDIRECT --to-port 3128
Ou tente encontrar números de linha (iptables -L --line-numbers) e use:
sudo iptables -D [number]
O segundo deve funcionar definitivamente.
Ou tente uma terceira coisa:
sudo iptables -F
sudo iptables -X
sudo iptables -t nat -F
sudo iptables -t nat -X
... você deve ter sorte com um desses.