Para Linux, considere o FFmpeg - ffmpeg.org/
Eu tenho um MP3 player antigo e temperamental que não lida bem com MP3s com coisas sofisticadas, como uma taxa de bits variável.
Existe uma ferramenta de linha de comando para Mac ou Linux que eu poderia usar para recodificar MP3s para que eles tenham uma taxa de bits fixa?
O LAME é provavelmente o nome mais conhecido nos negócios, embora seja um sistema muito avançado e não para alguém "novo" na linha de comando.
Confira o link do MP3Packer, ele pode alterar os arquivos de vbr para cbr.