We still don't know why the problem occurred but we have a solution. We've ignored the instructions provided by ESRI and instead did this:1. Publish map service from provided .sd file2. Run Import Map Server Cache toolPresto! Cached map services work. Ryan