Is the Fine Stucture constant constant?
Another thing that would be changed by a varying fine structure constant would be that it would alter almost every electromagnetically mediated phenomenon. All of the spectra of atoms would change. What would also change would be the temperature at which atoms can no longer hold onto their electrons, since the strength of attraction between electrons and the nucleus would change. This would then change the redshift at which the universe becomes transparent. The end result would be that the cosmic background radiation would be coming from a different time in the universe's history than otherwise thought. This would have consequences for the values of cosmological parameters.
Once you alter phenomena in this stage of the universe's history, though, you have to be quite careful to not disrupt the current predictions for how much hydrogen, helium, and heavy elements there are in the universe (while creating nuclei depends mainly on the strong interaction, electromagnetism does have something to do with determining the final energies of the nuclei, and so can't be completely neglected--changing the fine structure constant changes these cross-sections). Current theory predicts these things with great accuracy, and changing things around, particularly particle physics parameters that govern the length of the neucleosyntheis era (which overlaps with, but is a subset of the time at which the universe is opaque) potentially make these observations not agree with theory.
Many very accurate measurements seem to imply that the fine-structure constant has been totally constant, within the error margin, since the Big Bang. And the few experiments that suggested otherwise have problems. Theoretically, it's likely that the fine-structure constant is completely constant.
However, if you imagine that the fine-structure constant changes a bit, many things become different. For example, the stability and lifetimes of the neutron and nuclei will change abruptly. The modified fine-structure constant will also influence many other "constants" that define particle physics - such as the ratios of particle masses, fine-structure constants for other forces, mixing angles, and others - but you would have to describe what (dimensionless parameters) you want to keep fixed while you're changing the fine-structure constant.
From an "anthropic" viewpoint, it is important to notice that chemistry (minus nuclear physics, the care about isotopes etc.) would remain largely unaffected. It's because the atoms exist in the non-relativistic limit, and the fine-structure constant only determines the (order-of-magnitude estimate of the) speed of electrons in the atoms. Because the fine-structure constant is much smaller than one, the electrons in atoms may be approximated by non-relativistic mechanics. That would still be true if you e.g. doubled the fine-structure constant. So the ratios of the atomic frequencies etc. would remain pretty much unchanged, even if you doubled alpha, up to small corrections and splittings of the spectral lines (which are called the fine structure for a good reason).
It is even plausible that as complicated molecules as the DNA could continue to work unaffected even if alpha were changed by many percent or dozens of percent, despite the fact that the functioning of the DNA depends on small detailed in energy differences. If the units were redefined properly, the world of biochemistry would be pretty much unchanged. However, that's because the quantum electrodynamics with electrons only depends on one dimensionful parameter only - the electron mass - and one dimensionless one - the fine-structure constant that moreover defines a different scaling for space and time in the non-relativistic limit. If you considered the behavior of high-energy physics which has many other elementary particles, a change of alpha would surely make a difference.
Best wishes Lubos