Hi Mike,
I used the same MXD and updated the extent to match the new image, but this did not change the extent of the TPK in the Runtime. When opening the TPK in a new instance of ArcMap, the display is centred on the top level tile, but I'm not sure if ArcMap checks the extent of the data and updates the display accordingly.
I also recalculated the statistics and rebuilt the pyramids, in case the TPK was somehow picking up the old extents from this, but it didn't change the display in the Runtime.
However, your post made me realise I had not tried creating a TPK from a NEW MXD... This worked!!
I had a look in the extracted package folders created when viewing the TPK in ArcMap, checked the mapserver.json file and noticed that the initial extent and full extent were different for the TPK I was having problems with. The initial extent is correct for the updated imagery, but the full extent matches the old imagery. So it seems that the Runtime was looking at the full extent when displaying the TPK.
I'm still not sure what caused this difference, but now I will make sure I start with a new MXD for TPKs.
Thanks,
Matt