I know this doesn't exactly answer your question, but I would highly recommend using something other than Visual Source Safe. It has many problems and will only cause headaches for you in the long run. Unless you are mandated to use VSS (hopefully not), I would recommend something like Subversion or Mercurial. Save yourself headaches.
1) Use source safe client. Get latest all the code.
2) Open visual studio. Ignore all the errors.
3) Remove the missing projects from the solution. Add them back from their new path
4) Select change bindings within visual studio itself. Make sure the paths are correct. Click save
5) Save your solution and close. Then pray that the bindings worked.
Rinse and repeat every few weeks when your bindings break for no apparent reason.
Actually, the problem is within the sourcesafe binding files (vcssproj or some other funny extension which i cant remember now).
If you absolutely cannot get it to work, open your sln file in notepad and delete the bindings in there and try again.