I've been experiencing this issue off-and-on since upgrading to 10.3. After setting up a service to be published to ArcGIS Online, when I click the Publish button I get this error message. I have still managed to occasionally publish services successfully, but I have no idea what I did to get the publish to go through (closing down ArcMap and re-opening it is about as much as much as I can think of to do!)
I found this help page: ArcGIS Help 10.1 and moved a copy of the mxd/shapefiles to C:\temp as suggested, but still didn't have any success.
Anyone run across this error and figure out how to fix it?