Interesting you mention that - I actually got that Sparkfun LCD display for a different project, and had considered it for exactly this application.
The thought I had with it was to mount it above the CP, perhaps on the lower part of the bezel, and load in a graphic diagram of the buttons and their functions. Problem with that specific display is the size. Those were Nokia knock offs used for cheap cell phones, so they are quite small, around inch and a half on a side. You could maybe do it by giving each player's control set their own display (they are quite cheap, so multiple displays using a central controller would work), or using a larger central display (perhaps some kind of OLED, although that defeats the main advantage of that display which is cost).
Another thought I had was to code up a alphanumeric interface for it so it could be plugged into something like LCDsmartie (essentially a HD44780 emulation of sorts). I've built custom USB interfaces for these kinds of things before, in fact I even had the controller board picked out - the Atmel USBKEY demo board:
http://www.atmel.com/dyn/products/tools_card.asp?tool_id=3879Those are awesome little demo boards, and can be had on Digikey for $30.
It's a project to be sure, but definitely doable.