I recognize that this is an old post, but since there have been a few additional people with the same question I can tell you what worked for me when I have had this error....
Try opening ArcGIS Server Manager on your server, then go to the Services tab and choose 'Manage Services'. On the left hand side it should list all the folders for your site. If you open the 'System' folder you should see a geoprocessing service called 'Publishing Tools'. Try stopping and re-starting this service and then try publishing your map service again. You should be able to publish the service.
