I've just recently had similar problems.
I then decided to get both machines up to SP2 and the problems worsened! Well they appeared to worsen, but it seems SP2 has a few extra error messages up its sleeve.
Do you have the host and client IP's set manually?
This is the only way I've been able to get ICS to work properly.
On the client PC, I have the gateway as the hosts IP, and aldo the Primary DNS as the hosts IP address. This worked for me.