Usually when I hear that SecureNAT clients stop working but Web Proxy and Firewall clients continue to work, it makes me think of a DNS issue. The reason for this is that SecureNAT clients must resolve host names themselves, while Web Proxy and Firewall clients allow the ISA Firewall to resolve names on their behalf.
However, I now think of something else when SecureNAT clients stop working but Web Proxy and Firewall clients can still connect to the Internet. Now when I hear this, I think of receive-side scaling bug that was included with Windows Server 2003 Service Pack 2.
Read all about it here and check out the fix: