Philosophical background
For the user, the system is the user interface. This is actually the programmers' definition of an interface. You can change every other part as you wish, as long as the interface stays the same the users won't notice. As soon, as you change the user interface however, you affect users' life.
DA01 is right on that for data-heavy applications, albeit they have a really large learning curve, the keyboard is the best interface.
However, they're not intuitive. They don't really tell the user how they should be used. They usually require a handbook, internal help, and lots of training.
So the question is: how could you make clickable applications which could be still used using the same old keyboard shortcuts all your users are used to, while presenting fresh / untrained users with an intuitive interface?
Research Background
Learn everything you can about the following things:
- Jeff Raskin's biography, as he was a big fan of the keyboard
- The Canon Cat (Raskin has made it), and Archy
- The Humane Interface from Raskin (Pro Tip: Amazon doesn't offer a kindle version, but Safari Books Online has a digital version which you can read with their reader on iOS / Android
- Mozilla Ubiquity, the user interface designed by Raskin's son, Aza Raskin (a notable UX designer on his own right)
Perhaps it's a bit one-sided, all of it is Raskin stuff, but they still show you how to make an effective, keyboard-based user interface, something you can't find in the latest "how to design for Touchscreens like iPhone, iPad or Android" kind of books.
User research
Next thing: get a screen + keylog, and learn how people use the system. An effective tool for this would be the UNIX script command, which creates 'typescripts', which you can replay. Hopefully, there are no hidden character shortcuts, otherwise you may need keymon as well.
Making storyboards of original functionality
Next, draw a flow diagram, with each keyscreen connected with an arrow, and for each arrow, write down the keys which actually get you there. An example would be:

Enhance functionality
Here comes the trick: re-design each of the keyscreens with their graphical equivalent, ensuring, that the keyboard shortcuts stay the same between them
It can be that you don't need confirmation, but would rather like to have an Undo instead. Make sure that in this case the "y" to the confirmation gets eaten up without causing any errors (like, if an y comes within 1 second - cognitive barrier time for feedback - ignore it)
It can be, that the menu is not taking up a full screen by now, that's also fine, just make it highlighted when M comes, so they know they are at the right place. Give them feedback (based on the Norman book), just like what you'd do normally. Still, keep keyboard-level consistency.
Also, ensure that everyone has all the information at all the keyscreens to have the right decisions. For example, when saving a form, the form itself should be visible. This might not have been possible with the old interface, but this time, you have pixels to work with.
Make the user interface clickable
While keeping yourself to the previous rule, that is, keeping the system consistent, make it more-or less handable by GUI as well. It can be, that the GUI flows are a bit alternative,but the system should still respond to the same keyboard sequence the same way.
Give keyboard hints
In order to help new users learn the functionality, design a visual clue to handle keyboard shortcuts. An example could be:

(Not exactly aesthetically pleasing, but it's still nicer than a text-only interface I hope)
The perfect solution would be to handle these contextually, that is, enable them only when context actually allows their usage, this might, or might not be possible. Eg, a "Save" button could be enabled for click, but could be disabled for shortcut if there's another field in focus. Wether you show it to them with a disabled button (which is disabled both keyboard-wise and click-wise in its current state), that's up to you.
Also, you could allow users to hide these based on preference,it just frustrates the old guys, also those who prefer not to learn it at all, but helps transition perhaps.
Design a keyboard-based controller (devs task)
Tell the programmers the original Krassner & Pope MVC did think of MVC in a way that keyboards could be also used. This is actually the MVC what is quoted in the Design Patterns book. It might be a different model than what they're used to nowadays, but that's life. And again, this is actually a challenge: you have tons of users to support, with a literally easy to use interface! :)
Test prototypes with users
You'll have two group of users: those who know the keyboard shortcuts as muscle reflex / muscle memory, and those who don't. Test on both. You know, usual thing, story goal, try to go through the system and achieve the story goal, how did you feel, did it went well, think aloud, did it feel ok, where you lost at any point... UX research stuff.
Implement application
That's it. Tedious process, but a unique challenge to build an interface which is usable in a way we don't think anymore today of usability. I think it's worth it, this would be a pretty good adventure, I'm sure I'd love it. Then again, I have my own muscle memories myself, having started to use command line UNIXes in the 90s, I still use command line on OS X even to watch my movies sometimes, as it was the only way back then...
Or
Just wait for the old users to die out / leave company. That's also a solution.
Hope this helped.Enjoy the ride, seriously, this will be unique and fun, UX is about making the best experience for users, not about shininess!