I think usually restarting the phone app should clear the app, but you've done that already.
What you haven't mentioned trying is actually logging out of the phone app and logging back in. That fixes it for some people.
Another thing that sometimes works is hard powering off the headset. Press and hold the power button for 30 seconds.
Some users solved their problem simply by going into their Bluetooth settings on their phone and telling it to "forget this device" for the headset.
Similarly, this worked for some:
I think also, some users reported that the problem cleared itself after waiting a few hours for the servers to sync.
Another option would be to try using a different phone.
The last resort solution would be to try setting up the headset through MQDH, but the catch is that headsets set up this way cannot be re-connected to the phone app, so dig deep and search for other solutions first.
