On the machine you have left working, after formatting the other one and installing brand new shiny operating system, use the Network Wizard. At the end of this you have the option to make a network setup floppy disk. Make it.
Then run the floppy disk executable on every other machine on your network.
Voila! You should have a network. Assuming all machines are running Windows of some flavour or other and not Linux or something.
Note: Dunno why, but for some reason, with my network it always seems to take a minute or two before the network settings take effect. It wouldn't do any harm to reboot each machine after setting up the network, all machines should definitely be linked then.