I've seen this behaviour before... and when I have managed to get to the bottom of it, the problem usually turns out to be that two machines have the same IP. I most often encounter it when Mac's reappear on the network having been asleep for longer than their lease lifetime.