Well, where is the data? And where might it have got to. Have you moved it somewhere, or an IT guy changed srever names / addresses or whatnot.
As I understand it, when you publish an mxd map, a copy of it is made somewhere on the server, the mxd contains the pointers to the data sources, the symbolgies, layer visibility scale and so forth. THis is referenced by the service. So if the data is not where it is supposed to be the service will not work.