random workstations on network cannot browse internet or ping

I've spent countless hours trying to diagnose the problem. We did not
solve it.

Random Workstation running windows xp pro with a 192.168.4.x IP Address
Subnet 255.255.255.0
Gateway 192.168.4.1
DNS Servers 192.168.4.8 and 192.168.7.12

I could ping the server
I could NOT ping the Netscreen 5XP Firewall
I could NOT access the internet.
I could ping the localhost (127.0.0.1)
Event log didn't show any issues

We could RDP into the machine but still no access out from it.

DNS resolved addresses fine but could not ping or connect

Then all of a sudden everything was fine on the workstation I was on
and it could get out again and another random workstation stopped
working.

I physically connected the firewall to a different port on the switch.
I've rebooted switch and firewall.
Any suggestions?

Can anyone Help?
Thanks,
Erik