Essa sintaxe de invocação agora está obsoleta.
Na página de ajuda:
--proxy URL Use the specified HTTP/HTTPS proxy. Pass in an empty string (--proxy "") for direct connection
--cn-verification-proxy URL Use this proxy to verify the IP address for some Chinese sites. The default proxy specified by --proxy (or none, if the options is not present) is used for the actual downloading.
Então, a menos que você esteja usando proxies chineses, o comando deve ser:
youtube-dl [OPTIONS] --proxy 'http(s)://PROXY_URL:PROXY_PORT' URL
Escolher entre http ou https, dependendo do tipo de proxy.
Você também pode tentar testar seu proxy usando o urllib2 diretamente:
#!/usr/bin/python
import urllib2
import sys
url = sys.argv[1]
response = urllib2.urlopen(url)
html_string = response.read()
print html_string