Livestrong has a great page that illustrates a lot of points and references medical studies to support it.
Some key points:
limits extra muscle motion, or "oscillation" ... [which] reduces the amount of energy you are expending
assist[s] the hamstrings in controlling leg movement at the end of the swing phase ... delay[s] muscle soreness by compressing the muscle tissue enough so that less damage occurs
reduces impact force to muscles by 27 percent
increases the amount of lactate retained in muscles and thus reduces the amount that is released into the blood
Compression from the shorts may protect against a venous thrombosis
Compression shorts may help cool the body by wicking sweat from the body and allowing it to disperse faster
Take a look at the page for more details.
From a personal opinion standpoint, I find that the shorts also offer much needed support for the man-specific area. :) I can't say that I've ever experienced any negative side-effects from using compression gear. If the gear is too tight and worn for a prolonged period of time I'm sure it can cause damage, but that would fall under misuse and isn't really a side-effect of the compression material. I've worn compression sleeves for shin splints for an entire day/night and didn't see any negative impact.
As for why they are banned, I can only speculate. There is a difference between bike shorts and compression shorts, the most important being the padding (try biking 50+ miles without it, you'll understand). Because of the "scientifically proven" advantage that compression gear can give, they are probably banning it to keep the race as natural as possible, similar to bans on items in most sports.