The power rating decision wasn't made because of the time it would take to implement. There actually is a skill rating used in matchmaking -- we just don't expose it to the player.
I've posted this before, but here was our logic. You can disagree with it if you want, and my intention really isn't to debate the entire idea here, but I wanted to try and illustrate why we thought this strategy could help to build community.
(I'll ignore the interesting argument that rating can never really measure your skill in the same way no single number can measure an athlete's skill. Number of wins is a sure measure of accomplishment, but that's not the basis for how relay racers or football player divisions are set up. It's hard to have a single number measure both success and who you should play against, especially when you start to consider team games.)
When you have an uber rating that completely defines you as a player, everyone understandably focuses on it. Having a good rating becomes more important than winning the game. In other words, playing the game becomes a means to the end of having a better rating. That feels strange to us since presumably we are all here because we like to play games, not because we somehow all like ratings.
Put another way, do you think a lot of players would take part in a system where we allowed you to increase your ELO score by 100 points by spending $100 US? Not everyone would, but I still bet there would be a lot of people who did. That sort of illustrates the obsession with rating where players might even opt out of playing the game to have a good rating. We figured rating-mania wasn't good for the community. Playing games is good for the community.
Ratings also discourage players from trying new things, such as different civs, maps or game options. Nobody wants to hurt their position on an uber ladder because they tried something new. Furthermore, a lot of players wouldn't even experiment with new strategies for fear of losing a game in order just to learn something. In fact, this is where some (though not all) smurfing comes from -- players start a new account in order to experiment rather than risk any harm coming to their rating for stepping outside of the normal way they play. Put bluntly, ratings lead to conformity and things like perfecting build orders rather than creative game play and exposure to new ways to play.
What we thought we would try instead was to conceal the rating score and just have lots of different ladders. That way if you couldn't compete on the Most Wins ladder or the Highest HC Levels ladder, maybe you could take a look at the Most Wins as British ladder, or the Best Economy ladder. It gives players more options of things to do rather than just give up because they can never break the top 20 of *the* ladder.
Now we happily admit this is a little bit of radical thinking. It is entirely possible that the community isn't ready for a change of this magnitude, or may not even like the change even if this alternate system accomplished everything we wanted it to. It's hard to tell the difference sometimes between criticism because the system isn't working as intended and criticism just because the system is different. Nevertheless, we do have plans to expose some kind of power rating to players and let them compete to try and better their rating. That seems to be what a lot of players want.
In some ways, it was an experiment, and any (good) scientist can tell you that experiments are not about finding the answer you want, but about testing a hypothesis. Perhaps our hypothesis that ratings are bad has been disproven.
Also note that it made a lot more sense to try the radical system first and then go back to the tried-and-true than for you to download say patch 4 and discover that your ESO rating was gone and replaced by something completely different. It's more digestible to try something wacky with a safe fallback position than to try the opposite.