Bluetooth woes: connected but not paired

Hi All,

I've just got a new phone, but can't get my Edge 530 to pair with it in the Connect app. Old and new phones are both Android, running the same version of the OS (9). If I start the pairing process with the Garmin Connect app, it just says pairing failed after displaying the correct 6 digit code on both devices.

If I pair the Edge with the system settings, than they connect, and the phone appears in the status menu of the Edge, but it is still not "paired", it is not getting weather data, grouptrack and other features are missing. Also it will not reconnect automatically. I have tried everything (turning everything off, on, removing the Edge from known devices list, reinstalling the Connect app, even resetting both devices and switching back to the old phone, and trying to pair that again to see what happens. Nothing seems to help. Any ideas?