One consideration to be aware of is that users can be strongly averse to change. You're fighting against that no matter how improved you make things.
Aaron Sedley (the author of the above article) and Hendrik Müller from Google did a presentation on the topic of change aversion at UX Australia 2012, specifically in relation to the transition from Google Docs to Google Drive (that link contains the audio of the presentation and a link to the slides). As an aside, notable UXer Jared Spool has rejected their claims, and his take should be factored into your decision-making.
Specifically on the topic of changing toolbars, Microsoft has seen a lot of criticism in response to their change from a conventional toolbar to their so-called "ribbon" UI, despite some compelling usability research being applied in their design:
An online survey conducted by ExcelUser reports that a majority of
respondents had a negative opinion of the change, with advanced users
being "somewhat more negative" than intermediate users; the
self-estimated reduction in productivity was an average of about 20%,
and "about 35%" for people with a negative opinion.
They've experienced similar complaints in Internet Explorer 9 when they moved to a more minimalistic toolbar. Here's an indicative one from the blog comments when Microsoft first announced the changes:
And in general, I'm more and more bothered by this trend going on for
the past several years of dumbing every program down to the lowest
common denominator. I think that if a program is not specifically
designed to help/teach people with little to know computer knowledge,
it should strive to make it ever easier for power users (so not
"experts", who don't mind command-line stuff and editing configuration
files and registry entries, or even mod code, at any moment of the day
or night - those will always find a way to get what they want :)) to
make the most of it (while of course not making the basic tasks
noticeably more difficult for the average user), not just focus on
"average and less" and setting the rest aside because they're too few
to matter in the numbers game.
In general, expert users are more resistant to significant changes, for the reason Spool gives in his article linked above:
In most cases, people hate change because they don’t like to suddenly
become stupid. Think about it. Let’s say you’re a day-in-day-out GMail
user. You’ve mastered the menus and commands. You have everything set
up exactly like you want it.
Now, suddenly, one day, you arrive at the design and it’s different.
All the familiar commands have shifted around. Several are gone.
Several are new. Doing those routine, simple acts are no longer
routine or simple.
Because of the changes, you suddenly find yourself unable to do the
things you once did. While some are smart enough to blame the
designers, most will blame themselves. And those people hate feeling
stupid, just like everyone else.
As a qualified graphic designer I would consider myself and most of my colleagues expert users in Adobe Photoshop. Personally, I almost never use the mouse to change tools, preferring to use the keyboard shortcuts almost exclusively. One of the most capable visual designers I've ever had the privilege to work with, however, knows almost none of the keyboard shortcuts, and targets everything with the mouse, despite having used Photoshop every day of his professional life over the last 10 or so years at least. While watching him take three times longer to perform some tasks than I would is absolutely infuriating, I wouldn't dare claim he was any less of an expert in the use of the application to achieve a result; he simply isn't as confident with a keyboard as with a mouse.
The conclusion, then, is that you should assess the realistic usage of the toolbars as they exist in the application today. If the people who are currently dependent on the toolbar form a significant or even just vocal part of your user group, you might find it more trouble than it's worth removing the toolbar.
Whatever outcome you choose, you're unlikely to get much of a UX consensus that it's worth eliminating the toolbar merely on the grounds of it being a lot of work to redesign the icons. We're kind of duty-bound to tell you to do what's best by your users, regardless of if it's what's best by your organisation or yourself. Only you can weigh up the relative benefit of good-for-your-users vs. good-for-the-project's-budget, since only you know your users.
