Eu resolvi o problema removendo o diretório de cache do Team Foundation Server na máquina que tinha problemas.
Aparentemente, as antigas referências a um antigo Team Foudation Server estavam causando alguns conflitos ao tentar se conectar ao novo servidor.
O diretório de cache está localizado no diretório Local Settings\Application Data\Microsoft\Team Foundation
. Exclua a pasta 1.0
para o VS2005 ou a pasta 2.0
para o VS2008.