Em muitas distros, o avconv por padrão não é construído com "--enable-libmp3lame". O avconv deve ser compilado com suporte a MP3 para utilizar o libmp3lame.
Minha solução de trabalho foi baixar libav do repositório git e construí-lo sozinho. Esta é a linha de comando de configuração que usei:
./ configure --enable-libmp3lame --enable-nonfree --enable-gpl --enable-libx264
Você pode verificar se o suporte à codificação de MP3 está ou não integrado ao seu avconv com esta linha de comando:
avconv -codecs
Você deve ver um "E" na segunda coluna de recursos para a codificação de MP3 funcionar:
DEA.L. mp3 MP3 (MPEG audio layer 3) (decodificadores: mp3 mp3float) (codificadores: libmp3lame)
Se a segunda coluna for "." A codificação de MP3 não está incorporada no seu avconv: "DEA.L." é bom ", D.A.L" é ruim.