ArcMap allows you to create layer names with special characters in them. ArcMap also allows you to create multiple layers with the same name in the table of contents. When you create caches, the layer names must comply with the file naming conventions of the operating system. You see this error message if one of these is true.
Open your source map document, correct layer names and remove any duplicate layer names, save the map document, then stop and restart the service to pick up changes in the map service.