When creating MXD files in ArcGIS for Desktop, it is sometimes helpful to group headings into unique categories. For example someone might want to symbolize and group a set of features that are proposed and depict them differently from ones that are actual. Within the legend, it is often helpful to group these features together. ArcMap currently supports this functionality (see graphic below).
However when an MXD utilizing multiple headings for symbology is used to create a feature service, the service creation process fails. Once the multiple headings are removed, the service will successfully publish. I'm not sure if this is an issue as well for ArcGIS Server so I'll tag that in addition to the ArcGIS Desktop and ArcGIS Online categories.
For desktop, it took a lot of trial and error to figure out what was going on (error messages didn't help much). Hopefully it will be incorporated into future updates with AGOL but in the mean time, it would be helpful to at least include this type of information in future updates of the online help and/or additional detail in the error messages when attempting to publish a map service.