This command run in the Developer Command Prompt for Visual Studio did the trick:
tf workspaces /updateComputerName:MyOldComputerName /s:"http://MyServer:8080/tfs/MyCollection"
It had to be run from the computer I wanted to assign the workspace to (that is how it gets the new computer name.