I recieved a very similar problem on two machines, one was a Windows 2003 SBS Server and another was WinXP SP3, within a 2 hour period of each other so I though it warranted discussing the solution.
For the server issue, I was recieving error code 150 when trying to start the ICS service. I disovered this error because the server could not browser the internet, download AVG virus updates or downoad POP mail. Basically anything internet related. Clients we OK as far as internet and local file/print sharing.
For the XP issue, I just could not browse the internet. I think it is noteworthy to mention that malware was discovered on the XP machine (Trojan.FakeAlert) as well. After removing the maware, lack of internet still existed.
The resolution on both was to reset the Winsoxk TCP/IP stack. The command on both computers is the same.
From a command prompt:
netsh winsiock restart
*A reboot is required.
Other usefull Winsock repair / maintenance commands:
To backup a configuration :
netsh -c interface dump > c:configsofficeinterface.txt
To restore a configuration :
netsh -f c:configsofficeinterface.txt
Repair/reinit the TCP/IP protocol if it has gone bad (Useful as WinXP cannot uninstall the TCPIP stack netsh int ip reset
More info MS KB Q299357
