Your answer is clear but I can't find this option in ArcGIS 10.1. I have just recreated tiles in 10.1 and it looks even worse than 10.
To be honest you should prepare new manual for caching in 10.1 version because in short time it may occur as common problem.