Encryption protects a conversation with whoever holds the keys. Verifying is how you confirm that whoever holds them is the person you think it is — without trusting us, the relay, or the network.
It means the keys behind the conversation changed. There are innocent reasons — a reinstall, a restored backup, a new identity after a lost phone — and one that is not: someone substituting their key for your contact's. Z cannot tell these apart, which is exactly why it shows you rather than deciding for you. Ask them, over a different channel, before continuing.
The number is tied to the person, not the device. Linking a laptop to your account does not change it, so a change is always worth a question. Once a contact's post-quantum identity has arrived and been checked, the number covers that too — it never claims more than has actually been verified.
Your app tells your contacts which devices belong to you, signed by your account key, and their apps compare what they are told against what they hear from your other devices. A device added without your knowledge does not stay quiet — see devices.