I would first make sure that the data is visible in ArcMap at the same scales you can't see it in the service. If you can't see it, then that's an indication it's a spatial index issue. You can try to recreate the spatial index. You can also copy the data to create a new feature class or use the FC2FC tool, which would recreate the spatial index.
If you can see the data at all scales, then it's a problem with the Server, not the data. It's definitely not a permissions issue, as you wouldn't be able to see the data at all at any scale and the publishing process would tell you that the service couldn't come up as it couldn't find the data.
Definitely look at the logs under Verbose to analyze the different operations within the export map request. You should see data access, symbolizing, etc. There may be errors when trying to draw the data.
Also experiment with different data sources, similar to the suggestions in the first paragraph. If it's in SDE, export it to a FGDB feature class. If it's in an FGDB feature class, export it to a shapefile. Then, open a new map, add the data, and publish the service.