Any suggestions on where I start looking for the problem?

Do you connect to your ISP with PPPoE by any chance? If so that sounds exactly like what happens if the MTU on your machines hasn't been decreased. Most firewalls/routers that do pppoe and NAT compensate for you these days though. Do a google search for something like 'adjust pppoe mtu' for more info.

-Mike
_________________________
EmpMenuX - ext3 filesystem - Empeg iTunes integration