I have similar problem with my Pi 4 and the newest Raspbian to this date.
I can successfully connect and play YouTube, for example, on my Bluetooth audio system. But, after some time, during next power On, I observed - impossible to connect to my audio system. Error message similar (not same) as in the initial post. I have tried "sudo rpi-update", but this did not helps. The solution was - to remove that Bluetooth device (in Bluetooth devices menu) and add newly.
Just to check, after new success - I execute steps: shutdown, power off, audio system power off; audio power on, power on. And I see, that Bluetooth audio is working - no idea what happened previously.