Solve the Problem
Nice post. With any technology it's important at all levels to think about what problem you are solving, and how the technology you are installing provides a solution. In some cases the end users don't care or aren't impacted, e.g. if you move from legacy telephone services to an IP-based toll bypass, then the users shouldn't see a difference, but the company will save some money; great. On the other hand if you are redesigning the user experience by pushing IP telephony to the desk (and computer desktop), then as you say, training on that is critical - but so is understanding how people use the existing system, and how your new system will replicate that function. People are, as you say, creatures of habit, and if you're going to take away their telephonic cigarettes, so to speak, it's important to explain to them that there's an alternative, and here's how the new solution provides an alternative nicotine patch.
I think sometimes UC is not seen as being part of a user's daily workflow efficiency (beyond the things you hope will happen based on the brochureware), and how changing something so fundamental can severely impact the ability to function. At the very least if you know an old way of doing things will have to be addressed by way of an entirely new approach after a change, then prepare in advance and traing people up front so they're not left floundering after the fact. And remember that it's supposed to be about making the workflow efficient for the USER, and NOT for the convenience of the system behind the scenes.