You see this error message when you pick a tiling scheme that does not match the spatial reference of the data frame.
Make sure the spatial reference defined in your tiling scheme file matches the spatial reference of the specified data frame. Either change the tiling scheme file you are using or update the spatial reference of your data frame to match the one specified in the tiling scheme. After making changes to the data frame properties, be sure to save the map document. When working with a map service, make sure you stop and start the service to pick up the changes in the map document.