I agree with Rayraegah that you must think iteratively with legacy projects. I am heading up the UX and design of a similar legacy revamp.
Our product has two luxuries yours may not: 1. A suite of various products that do not rely on each other (users may use one or a handful of the 20 available, but not all of them) and 2. an infrequent usage per user (1-5 times a year).
Our product also has some drawbacks, which I'm sure yours shares: 1. Gigantic Frankenstein Syndrome (UI produced in chunks as necessary over 10 years, with very little mind for consistency); 2. Technically unsavvy users who will meet change with confusion, even if it is "more usable";
Given these luxuries and drawbacks, how we are going about changes is a dance between bold overhauls and unremarkable compromise.
We used a completely new product as a test ground for a much different visual UI. This was in the "bold overhaul" category. However, since the new look was only tied to a completely new product, there was no massive change for our users to balk at. The plan is for this new visual design to be applied to all products as they get redesigned. This kind of "pilot product" is a safe way to showcase new UI choices to internal leadership as well. Doing something like this calls for building internal alliances, so that when execs see something very different, everyone responsible for the project has each other's backs.
In a small project, I improved upon the UX using the old UI constraints. This is in the "unremarkable compromise" category. However ugly the UI is, a new visual style would look out of place. These kinds of projects I see as a fun design challenge (constraints are fun!) – to see how much I can change while staying within the bounds of what will be allowed.
Each project up for redesign needs to be weighed somewhere between these two, and building a consensus about the change with all involved is a good idea.
