The root cause of this issue is NuGet's CDN. We are currently working with NuGet team to resolve the issue (https://github.com/NuGet/NuGetGallery/issues/3961) and NuGet team is working with their CDN provider. Sorry for the inconveniences.
Posted May 16, 2017 - 11:44 PDT
Update
Some preliminary investigation makes us believe that the root cause is NuGet's CDN in US region as explicit resolving of api.nuget.org to a different CDN region (EU or TW for example) fixes the issue.
Posted May 15, 2017 - 17:14 PDT
Investigating
Starting on Thursday, May 11 we started seeing intermittent issues with downloading NuGet packages on our primary environment.
While we are investigating the root cause make sure your builds are using nuget 3.5.0 which is installed by default on build worker VMs and available in PATH. NuGet 3.5.0 has better support for timeouts/retries management. Also, to retry nuget restore use `appveyor-retry` script like that: