Getting the Guys at the Top to Buy-In
You raise a good point about the importance of getting buy-in from the top. Traditionally, IT seemed to be pushed as a bottom up approach. "We need X" and then you push a business case upwards until hopefully finance signs off. But with Cloud, since it's a transformation methodology that is really less about technology and more about changing the way your organizations creates value for customers, it really does need to be driven from the top down.
I find often Chief Marketing Offices (CMOs) can be a great ally for this. They are the ones with the constantly being cut budgets, the ones who are measured on whether the company hits its objectives, despite that it's really the Sales folks that drive the performance of the company (I could argue both ways, but traditionally strategy has come from Marketing, and so they are the folks with the most skin in the game). If they are shown that they can do things more efficiently, effectively and using tools that aren't plagued by legacy back end systems that are constantly touted as "this is how we've always done things.", there could be significant backing for the CIO who is trying to tie his streamlining projects into how it will transform the company in a tangible way.