There are two things that contribute to the stiffness of the structure (Well, actually more than two, but let's ignore the others for now!)
The "elastic stiffness" comes from the properties of the material (Youngs modulus, etc). That is what you use to calulate the frequencies, ignoring any stresses in the structure.
There is also a "stress stiffness" or "geometric stiffness", that is caused by the work you have to do when you move a body that has non-zero stress in it. A simple example is a string under tension. The string has almost zero elastic stiffness if you move the mid-point sideways, but there is also a stiffness proportional to the tension (or stress) in the string. This comes from the fact that if you move a point on the string sideways, you change the angle of the string , so a component of the tension force is now opposing the displacement of the string.
The geometric stiffness of a string with uniform tension is simple. In your tower example it gets more complicated because the axial stress (compression not tension) is zero at the top and increases linearly to the base. The change of stiffness along the length will change the shape of the vibration mode compared with an unstressed cantilever beam, as well as changing the frequency.
In practice you would make a computer model (e.g. a finite element analysis) to calculate the stress distribution, and then include both the geometric and elastic stiffness in the vibration calculations.
The geometric stiffness is also important in buckling analysis. In fact if the frequency lowest frequency mode was reduced to zero by the internal stresses, the structure would buckle. (But buckling analysis is not actually done this way, because buckling doesn't depend on the mass properties of the structure that are needed to do a vibration analysis).
For many structures this effect is small, but not always. For example the natural frequencies of large rotor blades may change by a factor of 2 or 3 times between zero RPM and the maximum operating speed.
