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?
The actual randomness of the points is irrelevant - this is just sample data. And in this case, this is 1-dimensional data - points have value and uncertainty.