É possível que o executável não tenha as permissões corretas.
Para estar em /usr/local/bin/youtube-dl , você provavelmente o executou com sudo make install ou similar. está lá como root:root , o que é bom, mas não vai dar certo.
Vamos definir o bit executável: sudo chmod +x /usr/local/bin/youtube-dl
Em seguida, tente usar youtube-dl .