Check the map document does open properly on the ArcGIS Server machine (open it locally – this way you easily find broken data source links, missing fonts etc.) and save it to the central map document folder.
Note: Recommended folder location is
<ArcGIS Server output, jobs, cache directory location>\ServiceDocuments
folder on the ArcGIS Server machine.
You should never open and edit map documents directly from this folder with ArcMap because it could happen that you change the map document (not deliberately of course). The changed ArcMap document will then be published finally without human interaction when ArcGIS Server Object Manager (SOM) recycles its server processes (Server Object Container, SOC). This happens because ArcGIS Server does not create an internal copy of the map document. Recycling happens every 24 hours by default.