Couple days ago I encountered an audio conversion failed: Unknown encoder ‘libmp3lame’ error when I tried to convert YouTube videos to mp3 format using youtube-dl.

$ youtube-dl --extract-audio --audio-format=mp3 -t https://www.youtube.com/...
[youtube] Setting language
[youtube] PL: Downloading page #1
[youtube] xxx: Downloading video webpage
[youtube] xxx: Downloading video info webpage
[youtube] xxx: Extracting video information
[download] Destination: xxx.flv
[download] 100.0% of 9.54M at  105.96k/s ETA 00:00
[ffmpeg] Destination: xxx.mp3
ERROR: audio conversion failed: Unknown encoder 'libmp3lame'

Hopefully this problem is answered at the answers.launchpad.net (Error extracting audio to mp3).

Quick solutions is to install libavcodec-extra-53 package:

$ sudo apt-get install libavcodec-extra-53