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.