In Georgia the ousted leader (Shevarnadze) was also corrupt and inefficient, but those who overthrew him were hand-picked and mentored in politics by him and had been his loyalists until they decided that they didn't need him any more. I am not sure there is much change there apart from personalities. The biggest challenge for the new government is how to deal with separatism in Abkhazia and South Osetiya, both of which, with almost open support from Russia have de facto become independent. After a few years of a bloody conflict Shevarnadze effectively dropped all attempts to reestablish Georgia's sovereignty over those breakaway republics, but the new leadership seems to be more radically nationalistic and this is a cause for concern (fortunately the action so far has been limited to rhetoric).
As for the Ukraine, the country had been split into two business and political clans (partly along the East-West division) all along. The "Eastern" clan that had been in power under former president Kuchma tried to foster its own commercial interests and the government was without any doubt extremely corrupt and inefficient. Its grip on power, however, was far from being absolute, so it never really came close to being a dictatorship. That could be seen even in the first election; although the vote counting was rigged, they could do as much as to throw in some extra 8-10% of votes for the pro-government candidate, and the power of the opposite clan was enough to challenge those results and win a decision to hold re-election. In contrast to Georgia, the re-election did not produce a landslide for Yushchenko but just a moderate margin of victory that was very much in line with what one could estimate from exit polls in the first election. This underscores the fact that the ousted clan still enjoyed the support of almost half of the population, especially in the ethnically Russian Eastern regions of the country. Most of my friends familiar with the situation hold the opinion that this was simply a clash between two politico-economic clans, neither of which is particularly committed to democracy or to eradicating corruption and inefficiency. However, the fact that the Yushchenko-Timoshenko clan had to enlist popular support and also Western support gives some hope that the country may make some headway toward a more democratic system in the long run.
As a general remark, the institutional change can happen only slowly and incrementally, so it would be totally unrealistic to expect "real and permanent democratic changes" to come out of a simple change in government. But the Ukranian case may contain the best long-term hope for such a change.

2) Are these events contagious?
It should be noted that all the three "revolutions" were triggered by national elections the date for which was determined by the Consitution. In this sense, they show that democracy is both not working and working in the post-Soviet republics. It is not working because instead of holding fair elections the ruling clans attempted to rig the results. It is working, however, because a popular revolt said "no" to this vote-rigging and because the transition of power did happen around the date determined by the Constitution, although it required street action to be implemented. In Russia, the next date set by the Constitution is 2008 when Putin will not be eligible for reelection (unless he attempts to change it, which by itself may trigger a revolt). In 2000 and 2004 there was undeniable vote-rigging but it did not affect the big picture as Putin clearly had the support of at least 60% of the voters. Especially in the 2004 elections the opposition simply disintegrated and, Hakamada's desperate run notwithstanding, there was not even a serious attempt to challenge Putin from the liberal, democratic flank. Since nothing is likely to happen until the next election in 2008 it is really hard to make any predictions at this point. It is not yet clear whether the ruling clan would be able to pick a unified candidate, and whether the ostracized oligarchs together with the liberal flank would be able to regroup and put forward a strong challenger. If they do and if there is a split among the ruling clan, then a situation similar to that in the Ukraine may play out. But this probably should not be called "contagion" anyway.