Also, this error can occur with an outdated version of nuget. Specifically, 4.0.0 exhibits this issue. Upgrading to 4.3.0 fixed the problem for me.
VSTS agents seem to use 4.0.0, so to work around this, there is a nuget version installer task which you can run as part of your build step to upgrade the version of nuget running in your build pipeline.