Have you checked for NAT?
The behavior you describe sound consistent with having the Linux box set up to perform NAT/masquerading, or behind a firewall of some sort. Have you looked into this?
Just to be clear, do you mean that you can communicate so long as you initiate the connection and STAY connected? Or do you mean that once you connect and disconnect to an outside host, that the host can then connect to the box (where it couldn't before)?