From Debian Wheezy, version 2012.02.27. I expect older versions to be able
to do it. The exact command I did is:

'youtube-dl --audio-format=mp3 --extract-audio
http://www.youtube.com/watch?v=sHjlM5A1jME&feature=related' and it saved
both an flv and mp3.

If you have an flv - any flv - try:
'ffmpeg -i video.flv -vn -acodec libmp3lame -aq 4 output.mp3' and share the
output if it doesn't work.