Annoying bug with no obvious cause!
I have been using Git (via Tortoise Git) to push code to VSTS. I've been using it all day and then suddenly, "Git did not exit cleanly- Authentication failed".
After re-entering my credentials about 5 tims, each time taking even more care that I was typing them in correctly, it wasn't making any difference.
I fixed it in the end by changing my alternate credentials in VSTS to the same password as before but it looks like the act of saving it had refreshed the privileges and then it worked.
You can get to that by clicking your name in the top-right of VSTS and choosing Security->Alternate Credentials.