[I worked for Microsoft for 10+ years, and now work for Facebook]

The main problem with Microsoft isn't strategy, it's the people. This is primarily why Microsoft has not been able to convert even good strategy into compelling products (Windows 8, for example).

This is not to say that strategy and employee organization are not important, it's just that those would be relatively easier problems, once the people problem was fixed. Conversely, you could fix strategy and even reorganize the company, but you'd just limp along until the people problem was fixed.

Decades of guaranteed profits from cash-cow products, along with rapid hiring with lax standards, has resulted in a bunch of mediocre managers and engineers rising through the organization. What the new leader needs to do, then is: fix the people problem.

In this answer, I'll propose some solutions that I've seen work successfully in Microsoft itself (I'm stealing from Terry Myerson and Steven Sinofsky).

There are three levels of people in any organization, and they have different responsibilities:

The top (leadership): In a company like Microsoft, the CEO doesn't come up with the vision alone; the company is big enough that vision comes from the leaders of the various divisions. I collectively call these "the top". These are responsible for coming up with the strategy and vision and then making sure it gets done.

How you fix this layer: This is easiest to fix. They serve at the discretion of the leader, and are easiest to replace. A new leader will bring his own team of excellent people in, and put them in charge of various divisions and hold them accountable.

The bottom (individual contributors and first-level managers): I am an engineer, and so, this section of the answer is going to be engineering-centric, but I hope it extends to other functions of the organization. Historically, Microsoft used to have very good engineers. For various reasons, the hiring bar has been lowered in recent years, but this should not be too hard to fix.

How you fix this layer:
The work of individual contributors can be tracked by broad metrics. Engineering work can be (somewhat) tracked by lines of code written, lines of code reviewed, bugs per line of code, etc. This is not perfect by any stretch, and I don't recommend using it to determine rewards, but it can be used to determine the lower 10% that needs to be fired.

I am also a big fan of Facebook's bootcamp program, where new hires are put through a 6-week program of fixing random bugs from parts of the system they know nothing about. At Facebook, you're expected to quickly ramp up and fix issues right from the get go.

I firmly believe that engineers (that includes PMs and testers) should be able to at least fix a bug. The same goes for first level managers. Believe it or not, many in Microsoft would fail this test. I would recommend Microsoft institute a bootcamp program, and require all engineers plus first level managers (that includes PMs) to take the program in the next two years. If you fail the program, you're out. Most of the incompetent people would not even bother, and just leave of their own volition.

A similar program would work for other non-engineering disciplines.

The middle (middle management): This is the hardest to fix. Middle managers can often coast on the work of their teams, and it is very hard to determine what value they add to the system. Yet, they are the ones can most deeply damage morale and hamper execution.

How you fix this layer:
One good approach, that Steven Sinofsky put in place was to reduce the layers of middle management. There should just be lesser of these around. Microsoft should implement this across the board.

The second approach, one that Terry Myerson used to turn around Windows Phone (yes, I consider it a successful turnaround, because I know the abysmal state of Windows Phone before Terry took it over). He simply replaced most of the middle managers, and brought in people he trusted. This approach is not fair, but is effective. Also, this is probably not implementable at the large scale of the whole company (there are legal issues).

In practice, you'd have to aggressively hold people accountable, and weed people out as soon as you could. In my opinion, this is where Steven Sinofsky failed - he was unable to clean out crappy middle management as quickly as he should have.

Page-rank for people?
Lastly, I think it might be interesting to implement something like Google PageRank for people to weed out the bad people. Ask every person to list out five of the best people they know, and use this to evaluate the globally best (and globally worst) people.

Conclusion
The key strength that Microsoft still retains is a core of great people who have stuck through the company and have been rewarded well. Microsoft needs to rebuild itself around these people.

P.S: It goes without saying, but I'll add the disclaimer that these are my personal views, and do not represent my employer.