The tiles can be different image sizes, but the LOD (levels of details) need to match. In your two map services, they were cached for different sets of LODs: {"level" : 0, "resolution" : 4096, "scale" : 15480944.8660992},
{"level" : 1, "resolution" : 2048, "scale" : 7740472.4330496},
{"level" : 2, "resolution" : 1024, "scale" : 3870236.2165248},
{"level" : 3, "resolution" : 512, "scale" : 1935118.1082624},
etc {"level" : 0, "resolution" : 2560, "scale" : 9675590.541312},
{"level" : 1, "resolution" : 1280, "scale" : 4837795.270656},
{"level" : 2, "resolution" : 640, "scale" : 2418897.635328},
etcTiled map services are only displayed at the scales they were created for. If you re-create one of them to the match the other, things should work fine.