New iPhone update:
I kept futzing with this new phone, getting the same message over and over. It also told me calling Apple Support could not speed up the process of changing my password.
I then had a crazy idea: I used my HP laptop and logged into Apple.com. I followed its instructions about setting up a new password, which echoed everything my phone had told me to do. But, i tried one more time and a different password which i have no memory of assigning to Apple, and it worked. It "took".
I am not fully functional yet, because all my apps must complete their download now that the system knows it's "me".
Will keep you posted.