I've got 2 computers in a network, 1 with a dial up connection connected to another computer with a crossover cable. I've enabled internet sharing (with the wizard) on each end, and created a shared internet connection between them. I can remote into the slave computer with the host, the host see's the slave on the network, but the slave doesnt see the host. When using the slave to look for workgroup computers, I keep getting permission errors with the workgroup. The shared connection is established though, or it says it is, but I dont get a connection to the internet. I get a correct IP address, and the gateway of the slave is the ip of the host. When connecting to the internet, the DNS is resolving IP names, so I'm nearly there...Everything I've read tells me it should be working. I have a feeling it has something to do with the fact that the slave computer can't see the host through the network, nor can it ping it. Yet, it shows a shared internet connection with the host as connected.
I think only the host needs to have ICS enabled on the dialup connection. The slave don't need to have ICS enabled.
Anyway, run through this article http://support.microsoft.com/kb/306126 and see if you have done everything according the steps in there. It is pretty straightforward and easy to follow.