Well, after following the troubleshooting steps, the issue has gotten worse. I can no longer connect to any bluetooth device at all for longer than one or two seconds. Trying to clear storage and cache on the bluetooth system apps to see if that works at all.
You might also try resetting the network settings on the phone. That sometimes solves Bluetooth connectivity issues.