WinXP Internet sharing

I have two computers, one with a dial-up connection which is set to share this connection on my LAN. (I know I know, just get a better connection than dial-up, unfortunately where I live prohibits this, at best I may be able to get satellite or something, but it’d be prohibitively expensive) Both computers are windows XP professional, with pretty much default settings, standard on the computer sharing, and DHCP getting an address from that computer on the other. They’re connected by a crossover cable. I’m pretty sure its all configured properly, its a pretty simple setup with nothing unusual.

Heres the problem: Everything technically works OK, the computer that directly connects has no issues, however the computer that is being shared the connection has a weird problem. Whenever I try to connect to a site for the first time, it instantly comes back with page not found. And its pretty damn consistent about this. If I then try to connect to the site a second time it works perfectly and I can browse the site fine. If I leave it for about 5 minutes, it starts saying page not found again on the first try. I’ve also noticed the google homepage seems to work fine all the time, but thats about the only exception. I use firefox, but begrudgingly opened IE just now to test it, and, same thing happening there too.

Any ideas on how I could fix this?

My best guess here is that a firewall is interfering; either Windows Firewall or a third party one you have installed - do you have exceptions set up for ICS in the firewall?