This isn't impossible at all; I've done it a million times. Maybe you're thinking it's impossible because you think the GUI has to
understand the prompts from the command-line program; that's not the case at all. Instead, it just has to properly
react to them, and the way it does that is because you program in the correct response for every possible prompt. The first thing you need to do is create a flowchart on paper, or a state machine using a FSM notation, which represents the flow of prompts and inputs. Although you can't modify the source, hopefully you can look at it, as this will make it easy to verify that you've covered all the possibilities.
So you write a separate program to be the GUI. The GUI program uses Runtime.exec() to start the command-line program. It reads from the Process output/error streams, and write to the input stream using a set of independent threads.
Imagine you start the command-line program and it says
Your GUI program knows (because you know) that these are the options when the program starts up. So your GUI has a menu (let's say) with four commands: "Defrag", "Install Linux", "Nuke", "Quit". The handlers for these four menu items are real simple: the last one just prints "D" to the process's input stream, while the first three each print a character to the stream, then put up a modal dialog (let's say) which provides a GUI for the corresponding sub-tree of the flowchart, with all the possible input information. If the program prints results or information, then your GUI program knows when this will happen, and reads the information from the streams at the appropriate time, displaying it in the GUI.
A tool like
ExpectJ is a big help in reading and reacting to the command-line program's output.