To test the influence of the surrounding medium on the relaxation dynamics of the plasmon band bleach recovery of gold nanoparticles after excitation with femtosecond laser pulses, we embedded 14.5 and 12.1 nm colloidal gold nanoparticles (synthesized electrochemically) in MgSO4 powder and investigated these samples by femtosecond diffuse reflectance spectroscopy. By measuring the relaxation dynamics over a wide range of excitation energies, we found that the fast decay component is slower by about a factor of 2 for the particles in the MgSO4 powder compared to those in solution while no significant change in the slow decay component is observed. In agreement with this observation, we found that adding solvent to the particles embedded in the powder caused a decrease in the relaxation time from about 10 ps to 5 ps for the fast decay component. This leads to the conclusion that the electron-phonon relaxation in these gold nanoparticles depends on the chemical nature and/or physical phase (solid vs solution) of the surrounding medium. A discussion of this in terms of the type of phonon involved, and the nature of the electron-phonon and phonon-phonon relaxation processes is discussed. To our knowledge, this also presents the first time that a transient bleach could be observed by diffuse reflectance spectroscopy.