AGS error: #000569: Failed to generate cache. All server contexts failed to cache map.

I was getting the following error when trying to cache a map service in ArcGIS Server/ArcCatalog: 000569: Failed to generate cache. All server contexts failed to cache map.

I ultimately resolved this issue by upgrading my server software (ArcGIS Desktop) to the same version as my client (in my case 9.3.1 service pack 1). Caching only within a feature, which in my case was a three county polygon that was much larger than the area I wanted to cache, greatly improved performance ... I'm not sure if it even would have worked without that.

Note: if postinstallation hangs while upgrading server software check out this post: http://support.esri.com/index.cfm?fa=knowledgebase.techarticles.articleShow&d=32766