In this letter, we present evidence for a mechanism responsible for the nonclassical nonlinear dynamics observed in many cemented granular materials that are generally classified as mesoscopic nonlinear elastic materials. We demonstrate numerically that force chains are created within the complex grain-pore network of these materials when subjected to dynamic loading. The interface properties between grains along with the sharp and localized increase of the stress occurring at the grain-grain contacts leads to a reversible decrease of the elastic properties at macroscopic scale and peculiar effects on the propagation of elastic waves when grain boundary properties are appropriately considered. These effects are observed for relatively small amplitudes of the elastic waves, i.e., within tens of microstrain, and relatively large wavelengths, i.e., orders of magnitude larger than the material constituents. The mechanics are investigated numerically using the hybrid finite-discrete-element method and match those observed experimentally using nonlinear resonant ultrasound spectroscopy.