You've duplicated constraints because if any one particle is constrainined in all three dimensions with all the other particles this constrains all the particles. The number of constraints is 3(N - 1).
To give an example, take three particles a, b and c. If a is fixed relative to b and is also fixed relative to c, then b and c are fixed relative to each other without having to introduce new constraints.
I think that the term "degree of freedom" had been initially derived from the observation that the system may be completely described by $n$ independent coordinates - they said: "well, if this $n$ is really a characteristic of the system - let's give it a name!". It is my personal belief that the name comes from a classical kinematics: if a body can't move "freely" in some direction - this reduces $n$ by one.
Therefore, your question may be reduced to the following one: "why the number of independent coordinates which describe the system completely does not depend on coordinates themselves?". Am I right here?
Mathematical answer:
We describe systems by means of linear algebra. There is a concept of a basis in linear algebra: a (minimal) set of independent vectors is a basis, while the projection of any vector from a state-space of a system on this set preserves the norm of the state-space vectors (there are many alternative definitions).
What the above definition says is that if you find a set of (independent) vectors, and can represent any state of the system in terms of these vectors without loosing any information - this set of vectors is a basis.
Why do we require the set of vectors to be minimal? Well, you can add another independent vector to this set, but if the system has no component in this additional coordinate - this vector is redundant. Real life example: you can describe the position of a body using three vector coordinates (x, y, z). You can expand this set of three vectors with a vector of velocity of the wind (which is clearly independent with any of the positional vectors of the body), but we need not worry what the wind is. We are measuring the position of a body.
So, we have a basis, what now? Well, there is a theorem in linear algebra which proves that if you have a basis for the state-space, and you find another basis, then the dimensions of these bases are the same. This means that you always need exactly $n$ independent coordinates to describe the system completely (without loss of information).
Intuitive answer:
This one is very tricky, because all the discussion about "coordinates" and "independence" is bound to the framework of linear algebra. Really, I find it very hard to reason the above statements intuitively.
Maybe this: assume that there is finite number of properties of interest in the system (as it is usually the case). You are given $n$ boundary conditions which are not related - none of them can be derived from the rest. In this case, each boundary condition allows you to express a single property of your system. If you find that these $n$ boundary conditions describe all the properties of interest - this means that you have $n$ properties of interest.
Now, if you're given with $m > n$ unrelated boundary conditions, you can express $m$ properties of your system. However, we have already shown that you have just $n$ properties of interest. Conclusion: the $m$ unrelated boundary conditions describe $m - n$ parameters which you are not interested in. Throw them away because they obscure your view.
Best Answer
The system has three degrees of freedom, but that doesn't mean that any three numbers necessarily specify the full state of the system. If you have $x_1$, $y_1$, and $y_2$, then as you have noticed there are two possible solutions to $x_2$. But you can fully specify the system with $x_1$, $y_1$ and an angle specifying which direction the second particle is in relative to the first.