No remote access (from Security forum)

This is a repost from the security forum. I am having trouble with remote access to a RH 7.2 box. Here's the scenario: no remote hosts (excluding my Win2k box on the same subnet) can access (ping, portscan, login via ssh) this box. When I login via console (or ssh from Win2k) the box becomes visible (can ping ,portscan, login via ssh from remote hosts). All networking is fine from the box itself. I have turned off all firewalls (iptables and ipchains). For all intents and purposes this box should be wide open. Funny thing is that I had the same problem with a FreeBSD 4.5 box and that's why I changed to RH. If I've missed anything please check my post in Security forum for further details. Any ideas anyone?