Problem with Internet Connection Sharing - it won't work with Windows Firewall.

[Nilrem]

Hi

I've been trying to get my brother in law's network working properly, the setup is as follows.

Cable modem connected to main PC running Windows XP home.
Main PC to switch, and onto 2 client PC's, a laptop and Xbox 360.

It had been working fine for ages, but about 2-3 weeks ago the client machines lost most (but not all) internet access.

As it stands now, the 360 can log into Live and play games.
All 3 client machines can ping internet sites - even sites that it cannot then load
All 3 client machines can access one or two sites (google and ntl for example), and start loading some other sites but never completing loading them or stalling after the dns lookup (on a couple of sites for example it manages the main banner).
MSN won't connect on the clients.
The Host machine has zero internet problems, and the 360 works fine online.

After much mucking about i've managed to rule out:
Problems with the clients - it was a long shot as it affected 3 separate machines (I used my router in place of the main machine).
DNS issues - pings work fine, but websites don't.
ICS itself - otherwise the 360 wouldn't work online, and the other machines wouldn't be able to ping.

The problems seem to disappear when I disable the windows firewall, but I cannot for the life of me work out why it's started to cause problems now, after a year+ of no problems.
What is really puzzling me though, is why a couple of sites load fine, pings work perfectly, but pretty much everything else doesn't work.

I've tried resetting the ICS setup on the main machine to try and sort it out, and trying different firewall settings with no luck, only turning the windows firewall off totally works to restore browsing etc to the other machines.

Has anyone got any ideas?
Is it possible to reinstall the windows firewall completely? (as it looks like it's a problem with that, and resetting it using it's reset option doesn't work).

Thanks