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 the gels. 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 understand 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.