This issue has been identified as a bug:
NIM080606: "An ArcGIS Online hosted feature service can only be overwritten if it is located in the user's root content directory"
This is the documented workaround:
1) Save a Service Definition file to the computer (instead of overwriting an existing service).
2) In AGOL, go the existing Service Definition file's description page and select the Update button to overwrite it with the new Service Definition file on the computer.