I'm not sure why you are being told that the order matters. Perhaps the plan administrator is confused by the requirement that there be no intervening distributions between the qualifying event and the distribution of the NUA shares for there to be a lump-sum distribution. The statutory requirement is just that to qualify as a lump-sum distribution (a requirement for NUA treatment), a total distribution must occur within a single calendar year and you must not have had any intervening distributions in prior calendar years since your qualifying event such as separation from service. By emptying the 401(k) within a single calendar year, even if done by multiple partial distributions, the Form 1099-R showing the distribution of the NUA shares should have box 2a Total distribution marked.
It's certainly possible that the plan has a plan-specific requirement detailed in the plan agreement, but I've never heard of a plan agreement that specified that the distribution of the NUA shares be done first. In fact, it would be clearer if the NUA shares were distributed last since doing so would complete the total distribution.
Still, what would be the problem with distributing the NUA shares later? With regard to taxation of the NUA shares, it doesn't matter when during the year the NUA shares are distributed. All that would matter would be the value when the NUA shares are subsequently sold. The sale of the NUA shares outside of the 401(k) does not have to be done immediately.
See 26 U.S. Code § 402(e)(4)(B) and (D)
https://www.law.cornell.edu/uscode/text/26/402#e_4