Shirley - can you give us more information? This leaves too many issues unknown.
1) what version of software are you using?
2) what is the data - is this elevation data, 32 bit floating point values? Are you caching a hillshaded view?
3) does the mosaic dataset appear to work normally at all scales, and it's only the cache that is failing?
4) you mention a map service; I would normally have advised an image service. Caching a map service starts at the smallest scales, then proceeds to large scales, whereas with imagery the caching starts at large scale. Have you tried an image service?
5) if this still fails, can you copy the verbose text from the caching tool so we can see what it is saying?
Thanks
Cody B.