If it wasn't for your mc/console problem, I'd have suspected an Xfont or gnome config problem.

What do you see when typing the following:

1) echo $LANG

2) cat /etc/environment