For the broken layers, try re-pathing them to their original source by right clicking the layer, opening the Properties, going to the Source tab, and setting the data source. If this is not successful for whatever reason, try disabling Spybot and then re-opening and re-pathing the map document thereafter. Based on your description of the behavior, it sounds like Spybot could have cleaned up something needed by the map document in order to connect to the layer data sources it needs but honestly doubt it. Do you have another computer with ArcGIS Desktop where you could try opening the same map document in order to see if the external services you mentioned break or don't break? Based on the fact that you said yours was working after running Spybot, the problem may not be Spybot at all... in fact, the user who reported this issue to you could simply have lost his internet connection which might explain why external links don't work. Can you access the REST URL for the external services via a browser from his computer?