Ok, so yes, first add the new scale using the Manage Map Server Cache Scales tool and then create tiles for the new scale using the Manage Map Server Cache Tiles tool. Again, you'll need to modify your map document first in order to produce a new service definition (SD) file to re-publish. Typically, I've had good luck with using group layers within a map document; one per scale level for my map service.