The problem you're having would sound very straightforward except for one thing: you said that with the Linux firewall connected directly to the cable modem or a hub it works fine and passes all protocols. Is that correct? Which kernel are you on? Can you try ping, telnet, and ssh and see if they work?