Solution: a recent Brave update added a new Brave Shields and Privacy setting called “Allow app links to open in apps outside of Brave”. Foolishly, the developers decided to have this new setting default to “Off”, which effectively disables Brave’s ability to open external app links.
Just find this setting and turn it On, and you should be good to go.