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.