The special thing about the users that had the issue are that they have full-control to a sub site but they only have read permission to the root web (the sub site had its permission inheritance broken). Furthermore, the root web is a publishing site. This would normally not cause any problems, but in SharePoint 2013 it apparently does, we first faced the issue in an on-premise installation, but I verified that the error is reproducible in SharePoint Online.
In the on-premise ULS log we found the following error, I’m happy that we didn’t have to resolve the issue in SharePoint online as it would have been a major headache without access to any logs.
'System.UnauthorizedAccessException: Access is denied. (Exception from HRESULT: 0x80070005 (E_ACCESSDENIED)) at Microsoft.SharePoint.SPGlobal.HandleUnauthorizedAccessException(UnauthorizedAccessException ex) at Microsoft.SharePoint.Library.SPRequest.GetMetadataForUrl(String bstrUrl, Int32 METADATAFLAGS, Guid& pgListId, Int32& plItemId, Int32& plType, Object& pvarFileOrFolder) at Microsoft.SharePoint.SPWeb.GetList(String strUrl) at Microsoft.SharePoint.Publishing.Mobile.Utilities.GetMobileChannelsList(SPWeb web) at Microsoft.SharePoint.Publishing.PublishingSite.get_DeviceChannels() at Microsoft.SharePoint.Publishing.Mobile.MappingsFile`1.GetCurrentDeviceChannelAliases(SPSite site) at Microsoft.SharePoint.Publishing.Mobile.MappingsFile`1.Update(Dictionary`2 mappingsToBeUpdated, Boolean forceOverwrite) at Microsoft.SharePoint.Publishing.CustomMasterUrlProperty.SetDirectChannelSpecificValue(SPWeb web) at Microsoft.SharePoint.Publishing.CustomMasterUrlProperty.SetDirectValue(String value, SPWeb web) at Microsoft.SharePoint.Publishing.InheritableProperty`1.SetInherit(Boolean inherit, Boolean forceAllSubWebInherit, String successUrl, String failureUrl, Boolean& updateRequired) at Microsoft.SharePoint.Publishing.InheritableProperty`1.SetInherit(Boolean inherit, Boolean forceAllSubWebInherit, Boolean& updateRequired) at Microsoft.SharePoint.Publishing.Internal.AreaProvisioner.SetMasterPageProperties(PublishingWeb area, Boolean& updateRequired) at Microsoft.SharePoint.Publishing.Internal.AreaProvisioner.SetLayoutRelatedProperties(PublishingWeb area, Boolean& updateRequired) at Microsoft.SharePoint.Publishing.Internal.AreaProvisioner.InitializePublishingWebDefaults()'
Looking closely at the error it seems that the user is getting an access denied to when the GetMobileChannelsList is called. You might be wondering what the mobile channel list is, but it is simply the new list that is used to specify the different device channels a new feature in SharePoint 2013 publishing sites. The device channel list is located at the root web and is a hidden lists that can be accessed from the UI by clicking on Device Channels from Site Settings.
For some reason when you create a publishing site, the list have unique permissions and the default is to only grant access to the users of the owner, designer and hierarchy administrator groups (The groups that have permissions varies with SharePoint patch version).
Thus if you break the inheritance at some sub web and expect a new owner group to be able to create publishing sites you will be seeing the above error.
The solution is to grant all users read access to the list by either adding their AD group, domain users, a SharePoint group that contains all users, or by remove the unique permission for list. The big question is why this list has unique permission per default, but only Microsoft can answer that.
As soon as the sub site owners have read access to the device channel list they will be able to create publishing sub sites.