Hi Andrew,
I have experienced similar issues as everyone here with 10.2. I recently updated ArcGIS to 10.2.1, but I still get the "packaging successful, but publishing failed" error.
I tested a couple of scenarios and this is what I've observed when trying to overwrite an existing service:
Received an error message if the following applies:
1. Moving existing feature service outside of root folder
2. Changing the name of existing feature service
The only workaround to this that worked for me is to keep the original feature service name and to move it from its current sub-directory folder back to the root folder whenever I need to overwrite a feature service. So far, everything seems to work after doing that.
At this point, I am not too sure if this is an issue that only I am experiencing. Do you have any insight on this matter?
Thank you,
-Gary