What version of Perl are you using? The reason I ask is because prior to 5.004, srand was not automatically called with the first call to rand. Not that I think this is likely here, but it's worth mentioning since you rely on rand so heavily.
Anyways, my gut feeling is that your distance metric is flawed. I'm no math wizard (I'm no *anything* wizard), but what happens when you do a Manhattan or hypotenuse distance measure between points, rather than considering only the x-axis?