Without verifying if these Ubuntu versions actually have my bad patch ("deprecate the Section member from package struct" - fixing the problem of a package changing sections basically being randomly in one of these sections) I would presume this is debbug #793360 aka: Never-Mark-Auto doesn't apply on the dependencies of packages with the given sections, but on the packages with the given section itself. Much more details there.
Without verifying if these Ubuntu versions actually have my bad patch ("deprecate the Section member from package struct" - fixing the problem of a package changing sections basically being randomly in one of these sections) I would presume this is debbug #793360 aka: Never-Mark-Auto doesn't apply on the dependencies of packages with the given sections, but on the packages with the given section itself. Much more details there.