Paul,
I have tested this bug extensively in 10.3, 10.3.1 and 10.4. I have come up with a workaround, which adds one additional step, that I verified with 10.4; as I have time I will test with 10.3.1 and 10.3. I attached screenshots of the tool I used with the City of Philadelphia Land Use Data.
1. Run Export Tile Cache Tool
Input Tile Cache: Select your input from the arcgisserver\directories\arcgiscache directory
Select your output Tile Cache location
Select your output tile cache name: I add _delete after the name--letting me know to delete later.
Export cache as "TILE_CACHE" not "TILE_PACKAGE"
Run tool.
2. Run Export Tile Cache Tool Again
Input Tile Cache: Select your output from step 1 (my case "LandUse_delete").
Select your output Tile Cache location
Select your output tile cache name: Final Name you desire (my case "LandUse")
Export cache as "TILE_PACKAGE"
Run tool.
For some reason, the format is invalid if you try and set your input to the arcgisserver directory. However, if you export the tile cache...as another tile cache first, then export your tile package, it should work. Let me know if you see the same behavior.
Regards,
Alex