How are you defining these "Euclidean distances"? Just using lat-long as x-y cartesian coordinates? That will work fairly well for small areas but at some point you have to realise that the X-coordinates are getting closer together at the poles.
If I'm standing two metres from the north pole my feet could be at maybe 30W and 30E (perhaps I do the splits...), which is 60 angular degree units apart in cartesian lat-long. But the north pole is only some tiny fraction of a degree unit in front of my feet. A euclidean distance algorithm would think my feet are thousands of times further apart than the distance from my feet to the pole.
Yes its extreme up here with the polar bears, but the spherical earth can muck up your distance calculations anywhere except on the equator.
Transform to a reasonable cartesian coordinate system if your data is in a small area, or use the full spherical distance.