Apparently mc (and ncurses in general) uses unicode for drawing its lines and boxes, and you need to enable this to make your display from these programs look right. Happily, this is really simple. In your .bashrc (or any other place that is convenient in your start up process) simply put the following:
This cleans up the problem right away, and mc and all other ncurses based programs now look like you would expect.
If you are using KDE, an althernate is to simply select "New Midnight Commander" from Konsole's Session menu. It does exactly the above, setting the TERM var to xterm before running mc. Of course, you have to be using KDE and Konsole for this to work...