Rheological measurements of model colloidal gels reveal that large variations in the shear moduli as colloidal volume-fraction changes are not reflected by simple structural parameters such as the coordination number, which remains almost a constant. We resolve this apparent contradiction by conducting a normal-mode analysis of experimentally measured bond networks of gels of colloidal particles with short-ranged attraction. We find that structural heterogeneity of the gels, which leads to floppy modes and a nonaffine-affine crossover as frequency increases, evolves as a function of the volume fraction and is key to understanding the frequency-dependent elasticity. Without any free parameters, we achieve good qualitative agreement with the measured mechanical response. Furthermore, we achieve universal collapse of the shear moduli through a phenomenological spring-dashpot model that accounts for the interplay between fluid viscosity, particle dissipation, and contributions from the affine and non-affine network deformation.