Have you tried a proxy? http://proxylist.hidemyass.com/ (pass as "--proxy <proxy>" to youtube-dl)