Unfortunately, i didn't found a solution for this error message or how to prevent it, but i use the following workaround to make my cache a bit more reliable.
first of all i check the given bounding box in the error message to control, if the cache exists or not, by viewing the published and cached service in a small javascript app. important: don't take a look of the service in arcmap. in most cases the cache was build.
next step is to update status.gdb --> manage map server cache status
next step is to copy your status.gdb to a new directory and open it in arcmap. now you can take a more detailed look in your status.gdb and you can control, which tiles (or bundles) have an error and are not succeeded. afterwards you can rerun the cache tool by defining an area of interest which contains the error-bundles.
that's how i cope with this error message or if i get other errors during cache. unfortunately, you can't be sure that your cache was build successfully when you get errors like this one. therefore i would appreciate it, if someone has a solution (or maybe an other workaround) based on this error.
regards