He's a smart man doing great things, but he's not perfect. Microsoft needs a new direction. Their assets are still valuable and have a huge potential for a great upside.
It's easy to play armchair CEO, but overall I'd say some new blood is needed.
For example, Mayer at yahoo may have been controversial, but she's turning it around.
I don't think some new ideas would hurt the company overall.
Source? She's trying to turn it around for sure but it is way too early to say that she's been successful. Her wins have largely been pr-wins which I wouldn't discount but there is only so many times you can cite your awesome weather app as evidence of a turnaround before people begin asking what more she's got besides the weather app.
Relevance is at least a start. You also can't say she's run it in to the ground as of yet either.
He is doing great work now and taking over the reigns of Microsoft would be like the president of the United States running for congress after he completed his term.
(An even better analogy would be if before the person was president they were involved with a different group of people, such as a theoretical President Ross Perot leaving the presidency to help rebuild Perot Systems.)
Microsoft should just buy out Valve Software to get Gabe Newell back, and then make him the new CEO. Gabe knows how to get stuff done, and he knows how to fix Windows and make great software.
Either that or buy out the old Atari in Europe to get Noland Bushnell as CEO of Microsoft.
Steve Wozniak is available for CEO as well, he seemed to like the Windows Mobile 8 phones.
Marc Andreessen formerly of Netscape has become a Microsoft fan and would make a good CEO.