We present a detailed study of the magnetic-field and temperature-dependent polarization of the near-band-gap photoluminescence in Gd-doped GaN layers. Our study reveals an extraordinarily strong influence of Gd doping on the electronic states in the GaN matrix. We observe that the spin splitting of the valence band reverses its sign for Gd concentrations as low as 1.6 x 10^{16} cm^{-3}. This remarkable result can be understood only in terms of a long range induction of magnetic moments in the surrounding GaN matrix by the Gd ions.