"distance is relative and depends on the reference frame." does not imply " There will always been some reference frame where their is no distance between points.". It just means that distances may be different.
Special relativity is a linear transformation, so a nonzero distance cannot become zero.
Relativity doesn't help locality violation, far from it. Relativity has issues (EPR) with locality violation.
Also, distance isn't really what locality is about; it's really about the causal sequence of events. If two events are close enough in time and far enough in space that light couldn't get from one to the other (in jargon: they're separated by a spacelike interval), then there'll be some reference frames where one happened before the other, and some where they happened in the opposite order. So if one of the events caused the other, there are reference frames where the cause came after the event.
So nonlocality violations imply that effects can come before causes in at least some reference frames. That's why people don't like it.