My answer is case specific.
From my experience, if they like their interface, and especially if someone who works in that company has designed it, you must not attack it no matter how bad it is. Once when you make enemy of someone who works there, you will have a lot of trouble to pass anything you bring in, no matter how good it is. They work there, and can "feed" stakeholders with their view.
When possible, it is necessary to present changes one at a time, AS improvements of existing design, which are result of advance in technologies/browsers etc. Only when you do couple of things well and they like it, you will get them to trust you and you will be able to introduce some bigger changes. Complete overhaul of UI is most efficient and fastest/cheapest, but is also probably too big of a risk. When you approach through iterations, you can "soften" decision makers gradually.
You must also think of their position, they don't want to be responsible for anything that is not good in new design, and when there is complete change they will probably dismiss it because they cannot test and be sure everything is better. It is safer for them to dismiss it and keep their position. But if they accept some small change (and their acceptance is not final in that phase), they will probably want see how that one change reflects to work process/user experience. However, this approach has major drawback - if you introduce changes one by one, that means that you can work without specification, and without real "target" - what is final product of your work. It is important to make that specification at start (no matter if it is only for you) so you don't loose composition if some "small" change requests arise. Also, if some of stakeholders is "designer", you could be in trouble, as they could suggest "next" change to UI (after you present current) which may not be what you planned to do, and you need to check if it fits in your spec before answering.