За @ комментарий Пески Я проверил версию NuGet, которая использовалась для этапа восстановления Restore в TeamCity.Используемая версия NuGet была 3.4.3.
Как только это было изменено на Nuget 4.3.0, восстановление пакета работало как ожидалось, и затем следующий шаг "Build Solution (sln)" завершился успешно.