> But can we really know the 6th coordinate? 

You are right -- given knowledge of five coordinates, there is a discrete choice (corresponding to a reflection) for the remaining coordinate. However, by convention we typically (but not always) use the word "degree of freedom" to mean a continuously varying quantity. This expresses the idea that you aren't free to choose the 6-th coordinate arbitrarily as an initial condition; you have only finite number of choices for it. Once you have chosen your initial conditions however, the subsequent evolution from Newton's laws is completely fixed and there are only 5 functions of time you need to solve for.

> If this is the effect of the constraint relation, then it doesn't really eliminate one redundant coordinate, but replaces the entire set, with one less coordinate. 

I agree with your description that what is happening is "replacing the entire set, with one less coordinate." However, I also agree with the "eliminate one redundant coordinate" perspective. We started with $6$ coordinates and one constraint, and ended up with $5$ coordinates and no constraints; regardless of exactly how this was done, it seems fair to describe the net *result* as "eliminating" one of the 6 coordinates using the constraint.