I need to add that this only happens if the Server site becomes disconnected from the config-store location, if on a shared network space...
Here's esri's official response:
NIM102777 When ArcGIS for Server loses connectivity to the config-store, the setting changes from 'public' map services to 'private', due to the loss of 'esriEveryone' principal.
The following workaround is available for this issue:
From Admin Endpoint:
1. Log in to the Admin Endpoint.
2. Select 'services" then 'permissions'.
2a. Select "clean".
2b. Enter "esriEveryone"
2c. clean.
3. Select 'add'.
4. For the Principal field, type 'esriEveryone'.
5. Confirm services are 'Public' by browsing to the REST endpoint.