Absent a competent physicist, I will have a crack at answering this.
First off, pure metals normally have a positive temperature coefficient of resistance (TCR), although as Paul Price has observed this is not always true for the liquid phase. As a matter of interest the paper from which he has quoted the bulk of his reply can be found
here.
As you observed in your question constantan is an alloy, but it is not the only one with a negative TCR. Bismuth, for example, exhibits a negative TCR if just a tiny amount of tin is present.
Another point to consider is that the TCR is an approximation over a limited temperature range. The relative resistance change vs. temperature function deltaR/R = f(T) is primarily linear for pure conductors, but alloys such as nichrome and constantan have nonlinear functions. Consequently the TCR is defined as the slope of a chord joining two temperatures on the curve. Depending on the temperatures chosen the TCR may be positive or negative for a given alloy.
For constantan the proportions of copper and nickel were adjusted empirically until the TCR was close to zero at around room temperature.
The exact mechanism is not well understood, but in constantan the occupancy of the 3d and 4s electron shells in an alloy of copper and nickel at a 60:40 ratio provide a structure which just compensates for the increased scattering caused by rising temperature.