Yes all the symptoms you are having are exactly what happened to me. I used to be able to surf through my slackware box, but all of the sudden I couldn't get through. Mine turned out that the wife's computer had a dup IP, but since you seemed to have ruled that out I would guess it is you NAT and IPforwarding. I'm not familiar with Mandrake, but there should be init scripts for the firewall and ipforwarding in either /etc/init.d or /etc/rc.d. You can manually start/stop these scripts to see what bearing this has on your network connectivity. If you do a man on iptables, you should be able to find a switch to list all your rules (and hopefully your active NAT rule). It might be -L.
