I had a similar problem due to a faulty switch in the network. Not only devices connected to that specific switch, but also others would fail to reach past the edge router to the Internet (besides failing to reach each other in a random fashion, of course). If you replaced ALL network devices in the network, of course, than that's not it. But, I thought I'd mention.