SOLVED:
If anyone else comes across this error for these Interaction Code flows, there are three places to enable it.
- On the org itself (otherwise you can’t set the next two)
- On the authentication server (this was missing for me)
- On the application
It is a shame the system logs did not indicate the failure in some way.