I've been playing around and here's what I've come up with:
Using a crossover cable I can have any two computers see each other, so I know the NICs are intact.
When Computer 3 (ICS server) has a fixed IP address (I gave it 192.168.0.1) the other computers can surf the net, but can't see each other through Network Neighbourhood. They can ping each other, however.
When Computer 1 is set to Auto IP the rest of the computers cannot surf the net; cannot see each other; can ping each other.
This is a solid a conclusion as I can come to, because it seems as though every time I restart the computers something changes. I even had it so that the computers could see each other through the switch, but couldn't surf the net. I have no idea how this happened, and the next time I booted they could no longer see each other.
I still suspect the switch. After all, if port 3 is fried then it stands to reason that the other ports may be damaged.
There are endless permutations of computer-to-switch that I could try, to try and narrow down the problem, but, to be honest, I just don't have the patience. I'm going to RMA this switch as soon as the clowns at D-Link call me back or pick up the phone.