Non-classical correlations play a crucial role in the development of quantum information science. The recent discovery that non-classical correlations can be present even in separable (unentangled) states has broadened this scenario. This generalized quantum correlation has been increasing relevance in several fields, among them quantum communication, quantum computation, quantum phase transitions, and biological systems. We demonstrate here the occurrence of the sudden-change phenomenon and immunity against some sources of noise for the quantum discord and its classical counterpart, in a room temperature nuclear magnetic resonance setup. The experiment is performed in a decohering environment causing loss of phase relations among the energy eigenstates and exchange of energy between system and environment, resulting in relaxation to a Gibbs ensemble.