When this happens, it means that the client actually is unable to decrypt the messages, and can do nothing about it if it can't obtain the keys somehow.
You have 3 options to fix it.
I'll assume you're on android.
The best is to go through with verifying your device. Then your other devices - those which have the encryption keys, the server doesn't and that's the point - will send all the keys they have to your new phone.
If you don't have those devices, but you have set up secure backup,
then the server actually has all your keys for safekeeping, but they are encrypted with a password that you provided (this is separate from the login password).
In this case you should be able to restore the keys by verifying your new device that way. It happens through the same dialog.
It's very, very recommend to set up secure backup, for everyone.
The third option is that if you have exported your encryption keys in the past, you can import them back manually. This is kind of the same as the automatic key backup, but this is stored where you choose instead of your homeserver, and it's not being made automatically.
Your can use the same menu for exporting and importing this way that.
If you don't see a banner asking you to verify your device, all 3 can be done in the "security & privacy" menu of the settings.
One more thing. If you still have the old phone, and you have not logged out of the client that you used, open the app there and it will send the keys to your old device, but only for the messages for which your new device has noticed that it doesn't have the keys.
To get all the keys through to the new phone, the easiest is to set up secure backup once (on any of them), and then verify both devices.
If it does not happen instantly, go to the "security & privacy" menu and it's "encrypted messages recovery" on your old phone, and have a look at what it says. It should say "all keys backed up" in the second row.
When that's the case, click "restore from backup" in the same menu on the new phone.
Don't forget to set up secure backup, though!
For the sake of simplicity I didn't tell before, but without that you can lose keys when you stop using an old device of yours.
This is because your old device may contain keys that other devices don't.
Your new phone, but generally every client app only downloads encryption keys for messages that it has tried to load at least once. This means, your new phone does not have the keys for old messages until you scroll up to all of them, and if you log out of your old device, or factory reset or lose it, you will lose those keys.
But when you set up secure backup, it uploads all of the keys to the encrypted backup store, and you'll not lose any of them.
And see, this right here is why Matrix is not ready for mainstream users. I've had the same exact issue. Key management with matrix rooms is hard as hell and really needs to be simplified. This is where something like simple X is better because it's a database, export, and the database file is encrypted and contains all the encrypted keys. So when you import the database with the password for the database, all the keys are there already.
It worked with the key. Matrix isn't the easiest I agree but so far it's the most promising one. I love simpleX's anonymity but it doesn't have matrix' traction. Simple X's algorithm combined with matrix would be awesome and p2p of course :)