addresses for both PCs, as well as the default gateway. Found in Network Properties, they should all be in the same range.

Next I would check if the non-Internet machine can connect if the other is off.

Fianlly ICS (Internet Connection Sharing) should not be used while a router is dishing out the IPs.