I know the user asked this for Linux, but I had this issue in Windows (10 64bits) and found little information, so this is how I solved it:
In case LIBAV does not help, try with FFMPEG, copying the contents of the "bin" folder to where "youtube-dl.exe" is. That did not help me, but others said it did, so it may worth a try.
Hope this helps someone having the issue in Windows.