Anki can only restore the original position numbers if they were preserved (that’s what “if possible” means there). It sounds you studied this before that feature was implemented, so the numbers probably weren’t preserved.
But luckily you have the card numbers as your sort field – that makes this easy to fix. Search up all the New cards in this deck – is:new deck:your::subdeck::name – and sort them by the “Sort Field” column. Select all and Reposition (start 0, step 1, uncheck both boxes).
If that still tells you it impacted 0 cards, or you don’t see the "New #"s change (in the Due column), then something else is wrong.
For the rest of your New cards in your collection, you can fix the ridiculously high New-queue numbers too. First run Tools > Check Database, just in case there are any issues in the New-queue. Search up all New cards that are not in deck you already adjusted – is:new -deck:your::subdeck::name – and sort by the “Due” column. Select all, Reposition them just like above (start 0, step 1, uncheck both boxes), and then run Check Database again to fix the index for the end of the New-card queue.