Just a tip: I had this issue with ArcGIS Online, where don't have the ability to change folder and database permissions, etc. I wasn't able to find the underlying cause, but in the end I managed to publish my service by running my map document through MXD Doctor beforehand. This might even help with ArcGIS Server if the other suggestions aren't working for you.