His/her ARP anecdote actually sounds like an STP problem, rather than ARP.
When an 802.1D capable bridge appears on a network with STP, the other bridges will all drop their forwarding table and learn again from scratch.
Failure mode sounds spookily like the one described.