OK, mystery solved: you have to disable the Talkback system app (I mean completely disabling the app, not just disabling it in the accessibility settings). I had this disabled in both pre-existing profiles, and it got enabled in the new profile. Once I disabled it, the app now no longer complains.
I guess that the Nordea app is going through all the enabled accessibility apps and checking signatures or something else, and it doesn't like what it sees.
This is unfortunately not unusual. BankID app in Sweden is also doing it, it refuses to work if it notices any accessibility app turned on that it does not like. At least BankID is helpful enough to show a dialog mentioning exactly which app it didn't like, and with a link to go to the settings and turning it off.
However, Nordea is even worse in the sense that is complaining even if the app is not turned on in Accessibility settings. Just it being installed is enough to trigger the error.
This is really getting out of hand, all these queries that apps can do are being abused for security theater. It would be nice if GrapheneOS could have a setting (even better if per-app) to hide accessibility apps from being enumerated.