I don't remember the transition from serial cables to USB being as bad. Yes, you needed adapters or new hardware, but USB has always "just worked". There are corner cases and limitations to it, of course, but USB was never (at least in my experience) anywhere near the headache that Bluetooth was... and still often is.
I use Bluetooth, and in most cases I even like it, but it's still way more of a hassle than it should be, especially for something that's been around as long as it has. I didn't realize it was around as long as you described.
I remember plenty of issues with USB device compatibility. Mostly when someone failed to follow the standards, of course—fully compliant devices and host controllers have generally worked well together, at least since USB 1.1. But there are a lot of non-compliant devices out there. Bluetooth isn't much different in that regard: if both devices follow the spec it tends to work well, but it's much more likely that one or both of the devices takes a "shortcut" or two in the name of saving a few cents. The fact that Bluetooth devices are typically battery-powered and thus strongly incentivised to cut corners to save a few milliwatts doesn't help.
However, the standards certainly aren't perfect even when implemented correctly. The most awkward aspect of the Bluetooth experience, in my opinion, has to do with pairing. There shouldn't by any limit to the number of simultaneously paired devices. They should just exchange signed credentials during the pairing process, and either device (but typically the more general-purpose one, such as the phone or laptop) should be able to present these pairing credentials later to establish a connection. The headphones, car stereo, or other special-purpose, storage-limited device shouldn't need to remember anything about the devices permitted to connect.
I use Bluetooth, and in most cases I even like it, but it's still way more of a hassle than it should be, especially for something that's been around as long as it has. I didn't realize it was around as long as you described.