Here are two possible solutions to try:
1) As Ian mentioned, resetting the data frame extent has helped me in the past. Ensure you are doing this through the Data Frame properties (overwriting the current full extent) and re-publishing the service.
2) Access the status.gdb for the service - open the Task Status feature class and determine the failed areas. Find the bundle name of the failed areas in the attributes. Go into the cache files on Windows Explorer and delete the problematic bundle files. Re-cache to the problematic bundle extents (not the failed areas from Task Status). This option has been useful in more cases of the "index is too large or too small" error.
I've come across a few other options to try as well per this thread:
Manage Map Cache Tile: Errors at 10.2.2
1) Using the exploded cache format instead of the compact cache format.
2) If you're using an AOI when you're caching, keep the AOI in the same gdb as the data being cached.
These have helped me and hopefully will help other people as well.
Here is what I found works:
Before you run the "Manage Cache" processes (like re-create or delete tiles etc.) run Convert Cache Format.
My theory is that in many cases the message is total bogus and the problem is not caused by indexes/extents/data/schema etc., and the process converting the cache format clears out any "locking" that actually triggers the failure. I'm using 10.3 but have seen this with versions 10.1 and 10.2 as well.
the repair geometry tool is what has helped me. I did find a data layer that appeared to have problems.