Same thing happened to me. Even though the phone never appears to fully connect, it’s stuck in there. You have to run the delete all bluetooth devices option and then your phone will become discoverable again.
My understanding is the issue has been fixed on iOS 16.0.3 onward. I recently tried with the latest 16.1.2 and now both phones work without issue.
So update your iOS to the very latest version. Delete all Bluetooth devices from panel, then try again and report back. Best of luck!