Does this happen only with a specific dataset or does it happen on any and all datasets?
If it's only happening with a specific dataset that you've previously been able to publish successfully, try this:
If you are trying to overwrite an existing dataset or republish a dataset that you had previously published but had deleted, it's likely related to the fact that there's residual information on the server-side that thus doesn't allow the dataset to be published as a new dataset but also doesn't have the requisite service definition information necessary for an overwrite to work. So, what you need to do here is manually upload the service definition file for the dataset using the web interface.
1. Using the web interface ('My Content'), make sure you don't see a service definition file or a layer file with the same name as the dataset you want to publish. If you do, delete them.
2. Try to publish again. It will likely still give you the same error (that's OK). In the process of publishing, it will create a service definition draft file for the dataset. Typically these are located at C:\Users\<user>\AppData\Local\Esri\<Desktop version>\Staging\My Hosted Services.
3. Once you have the sddraft, use the 'Stage Service' GP tool on it to create a full service definition file.
4. Go back to the web interface and upload ONLY that new service definition file.
5. Go back to Desktop and republish the datset, except select the option to overwrite. Your dataset should now appear in the list of existing services available to be overwritten.
