Do you use a router or are you connecting through some other sort of NAT device? This is the cause more often than not...
I had a problem with that here too, and I changed something on the router and it worked OK after that. However, I cant remember what I did and our new router doesnt cause this problem for some reason
