Your original interface may well work well as a REST interface as well.
There are two big issues that you need to overcome.
1) Many GUIs have a workflow component built on top of the interface requirements. For example, a large form presented as several pages. These are primarily done for the Human users, as most Computers don't really care.
2) Modern browsers don't natively support all of the verbs of HTTP (PUT, DELETE, etc.).
The first one can be over come because the workflow can be simple presentation, with the goal being that they call the final REST call properly. Going back to the multi-page form example, on the last page of the form you can have all of the other pages embedded as, say, hidden fields. So, the final POST is simply all of the data necessary, just like a computer would do initially.
The second can be handled using a simple proxy. Specifically, if you want to do a, say, DELETE, you can pass the verb in to your proxy, which treats POST and verb=DELETE the same as a DELETE. Just ensure that your back end support both similarly. Or you can use Ajax on your pages to make the correct calls.
While the interface as presented via your GUI may not be "REST" at a pedantic, the underlying system IS, at least at a protocol level, because it all follows the primary constraints of the architecture.
Another thing you can do is accept URL Encoded forms as input, but return XML as output. The key here is that you can send along with the XML a XSLT stylesheet. Thus, when it's rendered in a browser, you get the full boat HTML with graphics, and buttons, and all the rest. If you call it via a generic client, you get pure XML with none of the "cruft".
You can meet halfway by using XHTML and microformats. The payloads won't be dramatically bigger than a pure XML payload, yet it's still normal, every day XHTML with CSS fun for rendering in browsers.