Check/Fix Date & Time
I tried a bunch of different things for an hour (including "Reset Network Settings" as suggested above) but nothing resolved the problem. Finally I found a thread advising to correct Date & Time, and it worked!! For some reason the date & time were wrong, so the device could not properly contact and sync with the Apple server (even though my Apple ID/password worked from other devices and on iCloud.com). By turning on "Settings - General - Date & Time - Set Automatically" it made the date/time current and connected successfully.
Note: I did a hard reset after correcting the date/time, and then had to put in my username/password when prompted a few times before it was accepted. I think this was the time it took for the date/time to update, but after a few attempts it worked/problem solved.