just fyi "error 999999" is a generic error message when there is no more info on the error. I'm assuming you looked thru all this already Automating cache creation and updates with geoprocessing—Documentation (10.3 and 10.3.1) | ArcGIS fo... ?
I know if I need to replace all the tiles, it is sometimes cleaner for me to do it in two processes, i.e. delete them first, then replace the empties. If I'm replacing the entire cache (not just an extent), I rename the file and let it recreate from scratch (then delete the renamed folder after I'm sure I don't need it). A system delete is faster than a cache delete.
Another thing to try is refreshing you Cache status, either by renaming/deleting the Status.gdb the \arcgisserver\arcgiscache\<service>\Layers folder and then recreating, or using the tools to refresh.
But if that doesn't work (and you've already done the typical restart of the servce and/or machine you are running the script on), make sure the "extent" item you are using actually exists....and if this is a new install and you are refreshing the cache that existed before the upgrade, make sure that your AGS admin account has access to the data, and/or you have it registered in the data store.