There is no single country that is guaranteed to be able to download "all" youtube videos. Countries can be blocked by the video uploaders, and there is no way to predict or prevent that. The best you could do is use a proxy or VPN service to disguise your server's IP address, and/or perhaps figure out which country or countries have the fewest blocked videos.
There does currently appear to be a problem converting at least some Vevo videos for both the free and paid-for versions. I am investigating the issue and will let you know when a fix is available.
Edit: Can I please get some verification that the problem is occurring for everyone, and not just for specific countries? I live in the US, so I can confirm that the issue is evident here.
Edit: Upon further investigation, I'm beginning to think that Vevo videos on YouTube may have recently implemented some kind of additional protection against downloads. I checked out the download links for Vevo and non-Vevo videos, and they are virtually identical in the code. Which seems to indicate that some additional form of protection is now in place on YouTube servers -- for only Vevo videos? It's early days yet, so I will continue exploring and keep you updated. Any feedback you guys can provide would also be helpful!