In case this saves anyone else a day of worry:
There's an important caveat in https://help.ting.com/hc/en-us/articles/205420458-Backing-Up-Your-Phone : "Android Sync ... Note, contacts saved locally on your phone that are not in your Google contacts will not be backed up by syncing."
Turns out that all my contacts were stored only locally on my old phone, so Google Sync and my new phone had none of them.
So remember that the First Rule of Backups is Murphy's Law. UNVERIFIED BACKUPS NEVER WORK. ALWAYS VERIFY YOUR BACKUPS.
If you are depending on Android Sync for backups, log in to http://gmail.com , select Contacts in the dropdown at lower left, and confirm that your contacts are there.
(The fix on my old Android 4 phone, by the way: in Contacts, hit the menu/hamburger button at lower left, choose Import/Export, choose "Export to USB storage". After that's done, choose Import/Export again, choose "Import from USB storage", and under "Save contact to", choose Google.)