I had this issue when using Microsoft’s Team Foundation Service from Visual Studio 2012. I had just created the new team project via the TFS website. Although I could see my new project in the ‘add solution’ window, I got the error the OP reported.
I had to go into the “Team Explorer” window, then into “Connect to Team Projects” and tick the new project. Then I was able to add my solution to the team project.