Seen this happening several times and on several different systems for no apparent reason. Just lately, it has started occurring on a system that was previously working a week ago, so now I have a bunch of map services published that I can't overwrite nor create new services.
1. I have Advanced license level
2. I have over 50GB on both C and D drives - switching the staging folder to either makes no difference.
3. Tried renaming path names etc. but no luck.
Strangely, I have 3 MXDs that publish fine and 3 that refuse to. I can't see any differences to indicate why some work and some don't.