You and 401(k) provider are correct that new hires with lookback year pay below the HCE threshold are NHCEs initially and, if other eligibility criteria are met, if any, they should be eligible to enter that plan and defer until the first plan year in which they become HCE.
Unless eligibility for the NQDC plan specifically excludes any employee eligible for the 401(k) plan, it is determined independent of that plan. Also, the determination of "highly compensated" for the NQDC is different and independent (I'll use HC). HC for that purpose is someone considered highly paid in the context of the employer, and someone could be HCE for 401(k) but not HC for NQDC, or vice versa but that is less likely. There is the 20% top-paid group election that can be made for 401(k) HCE. For NQ, there is no formal 20% rule but there has been IRS opinion (I think) that to be predominantly for the benefit of HCs a NQDC cannot cover more than 20% of employees.
Your NQDC provider is correct in saying the employer must determine who is or is not in the top-hat group (select management and HC). If you use generic definitions, be sure that any management or compensation thresholds are not too low/too broad.
In summary, new executives could be eligible for both the 401(k) and NQDC for their first (partial) year or two of employment.
I hope this was helpful.