It would be a huge operational cost in environments that don't have automated certificate management in place, which, in reality is the vast majority of the operational environments in the world today. In fact, in most environment little to nothing is automated. We've just started seeing people dip their toes in those waters in the past few years, and most mainstream organizations only in the past year or two.
So, when making a modification to server (like replacement a certificate) requires a purchase order, a manual deployment by a server admin, and a 4-6 week change management process, and you multiply that by, say 10,000 times for a moderately large-ish organization, short-lived certs go from being a challenge to an impossibility.
Certainly there are organizations (like Google, for instance) who have this nailed, at least on their public properties (I don't know if their enterprise systems get the same attention) and it will start to invade the mainstream with tools like Let's Encrypt's ACME client. But that hasn't existed for long, and there was nothing else out there before that made this easy for a organization that isn't sophisticated to implement. Add that to the fact that fake or stolen certificated haven't been a massively widespread or expensive problem organizations have needed to struggle with, and there wasn't really any incentive to invest in a solution. The real answer is to make short-lived certs cheaper and easier to manage than long-lived certs. That is when they'll take off, and why Let's Encrypt holds such great promise in this area.
