saw Revolutions last night(it was great) so didn't spend much time on this before going to bed.
The default terminal does not list very many encoding options. None of the alternatives mentioned here(CP437, CP850, etc) were listed. I tried launching xterm with the -en option and would get warnings along the line of "no CP850 encoding, defaulting to ISO8859-1". Also tried the MonoDisplay font and got the same display results as the other fonts I'd selected.
Thinking back, I've had this same issue(with a CLI program) on an older Red Hat release and was able to get it working. As such, I suspect the issue is related to the missing encoding options.
Due to other commitments I won't be able to do anything else with this until Sunday.