Правильно предполагаете. mc - консольная программа, и как любая другая консольная, она требует терминал (консоль) для запуска. Тут придется вручную ярлык подправить.
Берем в качестве исходника ярлык из меню пуск, который там появляется при установке mc, вытаскиваем его на рабочий стол. Дальше открываем его (у меня - mc.desktop) любым тектовым редактором (xed подойдет). Правим так:
Ищем строку "Terminal=true" - правим на false.
Ищем строку "Exec=mc" Правми так: "Exec=mate-terminal mc"
Сохраняем.
Готово.
Вообще, правильнее было бы найти какого лешего DE лезет за xterm в качестве терминала, и подправить это поведение, но мне лень.
Можно еще симлинк создать в /usr/local/sbin/xterm -> /usr/bin/mate-terminal - по идее тоже должно сработать.
Ну и можно еще тупо xterm доустановить.
(В репах есть разумеется.)