I keep mentioning this, but people apparently aren't paying attention, and keep hijacking this thread with generic "My mouse doesn't work but my headphones do" Bluetooth problems that are fixed by a SMC reset.
Again, there are TWO problems being discussed in this thread.
One is generic bluetooth issues that are resolved by removing .plists and resetting the SMC as Apple suggests, and is not the "serious problem" first identified in this thread.
The second one is a VERY SERIOUS issue where the Catalina update essentially *wipes out the device firmware on the chip due to a corrupt or interrupted DFU update*. THIS is how the update is causing a hardware problem. This is what happened to my Mac Mini, and the only resolution was to change out the logic board.
The symptom of this is a "Bluetooth Unavailable" no matter what you do - whether you roll back to another version, and NO bluetooth devices work. This IS a hardware problem CAUSED by the Catalina update that IS CURRENTLY NOT USER FIXABLE. Apple has released firmware patches in the past, but they have not acknowledged this issue. I have now seen it on three people's devices.
I wish people would stop mucking up this thread with "one device works but the other doesn't" general Bluetooth compatibility stuff.. That is NOT the issue that provoked this thread, you guys are having typical bluetooth problems.
If you are stuck with the consistent "Bluetooth Not Available" and the device is NOT Present in System Information, your bluetooth chip firmware may literally be gone, and right now the only resolution is a hardware repair. That's what I had to do, and the "Genius Bar" verified this was the issue.