Using 23Na NMR measurements on sodium cobaltates at intermediate dopings (0.44<=x<=0.62), we establish the qualitative change of behavior of the local magnetic susceptibility at x*=0.63-0.65, from a low x Pauli-like regime to the high x Curie-Weiss regime. For 0.5<=x<=0.62, the presence of a maximum T* in the temperature dependence of the susceptibility shows the existence of an x-dependent energy scale. T_1 relaxation measurements establish the predominantly antiferromagnetic character of spin correlations for x<x*. This contradicts the commonly assumed uncorrelated Pauli behavior in this x range and is at odds with the observed ferromagnetic correlations for x>x*. It is suggested that at a given x the ferromagnetic correlations might dominate the antiferromagnetic ones above T*. From 59Co NMR data, it is shown that moving towards higher x away from x=0.5 results in the progressive appearance of nonmagnetic Co3+ sites, breaking the homogeneity of Co states encountered for x<=0.5. The main features of the NMR-detected 59Co quadrupolar effects, together with indications from the powder x-ray diffraction data, lead us to sketch a possible structural origin for the Co3+ sites. In light of this ensemble of new experimental observations, a new phase diagram is proposed, taking into account the systematic presence of correlations and their x-dependence.