Cara o problema era nas regras de INPUT então só vou postar elas
LAN=192.168.1.0/24
# MSN-Proxy
iptables -t nat -A PREROUTING -i eth1 -p tcp --dport 1863 -j REDIRECT --to-port 1863
iptables -t nat -A PREROUTING -p tcp --dport 1863 -s $LAN -j REDIRECT --to-port 1863
iptables -t nat -A PREROUTING -p tcp --dport 25000:30000 -s $LAN -j ACCEPT
iptables -A INPUT -p tcp --dport 25000:30000 -s $LAN -j ACCEPT
#
# Bloqueio do MSN
iptables -t nat -A PREROUTING -p tcp --dport 80 -m string --algo bm --string 'x-msn-messenger' -j DROP
#
#Proxy transparente
iptables -t nat -A PREROUTING -i eth1 -p tcp --dport 80 -j REDIRECT --to-port 3128
### Regras INPUT
iptables -A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A INPUT -i lo -j ACCEPT
iptables -A INPUT -p icmp --icmp-type 0 -j ACCEPT
iptables -A INPUT -p icmp --icmp-type 8 -j ACCEPT
iptables -A INPUT -p tcp --dport 22 -j ACCEPT
iptables -A INPUT -s $LAN -d 192.168.1.254 -p tcp -m tcp --dport 3128 -j ACCEPT
iptables -A INPUT -s $LAN -d 192.168.1.254 -p tcp -m tcp --dport 80 -j ACCEPT
iptables -A INPUT -s $LAN -d 192.168.1.254 -p tcp --dport 1863 -j ACCEPT
iptables -A INPUT -s $LAN -d 192.168.1.254 -p udp -m udp --dport 53 -j ACCEPT
192.168.1.254 = ip do servidor onde estão firewall/proxy/msn-proxy
eth1 = interface de rede interna
espero ter ajudado