A seguinte opção para mc fez o truque para mim.
./configure --with-screen=ncurses
Eu também tinha outras opções, mas acho que elas são irrelevantes
--enable-extcharset --enable-charset --with-edit
Eu estava acessando o osx do Ubuntu. Aqui está a saída locale no osx:
LANG=
LC_COLLATE="C"
LC_CTYPE="C"
LC_MESSAGES="C"
LC_MONETARY="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_ALL=
E eu tenho xterm-256color como meu TERM.