Don't enable both the buildin XP firewall (ICF is switched on by default on SP1) and ZoneAlarm at the same time. Enable one or the other but not both.
I have had both on for over a year now but have never had any problems, probably doesn't do any good either, but still

Maybe I am getting to basic here but is it possible that they have :

1. Blocked access to internet explorer when it asked and ticked the remember this box

2. Hit the block all internet access button by accident.

3. Blocked schost.exe from the program control menu (this seems to cause problems with internet connections, although by defult ZA allows it)

I can't remember off hand where thee program access button is but I know its not hard to find , that would be your best place to start. Other than that if you are really stumped get a copy of Ethereal and don't forget to install Winpcap . That way you can watch exactly what the packets are doing. If you can't intrepret the results I or anywone on here would help you out