Are they both the same make/model of server with the same type of network card? How long do they say that the network cable is unplugged for before they confirm that the network is connected? Is this only on startup or is it intermittent during normal use?

Check your link speed and duplex settings on the network card. You may find that adjusting them helps - by default, most network cards are set to "Auto", which means the fastest speed that the card supports (e.g. 100Mbps or 1000Mbps) and full duplex. Some systems are temperamental with those settings.