You chose a tiling scheme that doesn't match the spatial reference of the map.
Make sure the spatial reference defined in your tiling scheme file matches the spatial reference of the specified map. Either change the tiling scheme file you're using or update the spatial reference of your map to match the one specified in the tiling scheme. After making changes to the map properties, save the project. When working with a map service, make sure you stop and start the service to include the changes in the project.