We use an external mp3 encoder when transcoding music, and don't ship it with MC for Linux, so please check if you have the "lame" package installed, and install it if missing.
The .deb packages would've listed those as recommended, but its easy to miss.