Bluetooth arbitrarily stopped working on Ubuntu after dual-booting to Windows

TL;DR: Bluetooth was working perfectly fine on Kubuntu, until I booted into Windows. Now, Bluetooth only works on Windows, and Kubuntu's Bluetooth icon says "No adapters found".

My Machine

I have a desktop with Kubuntu 14.04.5 (with HWE, kernel 4.4.0), and Windows 10. They're both UEFI installations, and I use GRUB for dual-boot. I have an X99 motherboard, and I recently brought a Wifi + Bluetooth PCI Express card from Gigabyte, that's powered by the Intel 8260 chip -- a chip with excellent Linux support. (The Intel 8260's Wi-Fi interfaces through a PCI Express x1 slot, while the Bluetooth connects through an internal motherboard USB 2.0 slot.)

The Good

Intel 8260 worked perfectly out of the box. Kubuntu immediately picked it up, and I was able to set up my Bluetooth speakers as an audio sink and play audio with little hassle.

The Bad

I rarely use Windows, but I booted into it yesterday. I connected to my Bluetooth speaker fine from Windows. After that I booted back into Kubuntu, and my Bluetooth adapter had disappeared.

Details

I know my Intel 8260 chip is fine and this is not a hardware issue because Bluetooth continues to works fine on Windows. It's just no longer working on Linux. Intel 8260's Wi-Fi also continues to work with no problems on both Kubuntu and Windows.

In addition, lspci still lists the Wi-Fi device:

08:00.0 Network controller: Intel Corporation Wireless 8260 (rev 3a)

But remember, the Bluetooth chip isn't interfacing through PCIE, rather, it's interfacing through an internal USB 2.0 header on the motherboard.

I also ran lsusb, and there were 3 devices that just said Intel Corp. I don't know how identify if any of them is the Intel 8260 Bluetooth. This is the full output of lsusb:

Bus 002 Device 002: ID 8087:8002 Intel Corp. 
Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 001 Device 002: ID 8087:800a Intel Corp. 
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
Bus 004 Device 002: ID 045b:0210 Hitachi, Ltd 
Bus 004 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 003 Device 005: ID 045b:0209 Hitachi, Ltd 
Bus 003 Device 004: ID 04f2:0833 Chicony Electronics Co., Ltd 
Bus 003 Device 003: ID 046d:c24d Logitech, Inc. G710 Gaming Keyboard
Bus 003 Device 002: ID 8087:0a2b Intel Corp. 
Bus 003 Device 006: ID 046d:c52b Logitech, Inc. Unifying Receiver
Bus 003 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub

Maybe Windows messed with the chip, and re-configured it or something? Or maybe something affected the UEFI XHCI/EHCI hand-off of a USB device? I really don't know.

This is the output of dmesg | grep -i blue:

[   11.371872] Bluetooth: Core ver 2.21
[   11.371884] Bluetooth: HCI device and connection manager initialized
[   11.371887] Bluetooth: HCI socket layer initialized
[   11.371889] Bluetooth: L2CAP socket layer initialized
[   11.371897] Bluetooth: SCO socket layer initialized
[   12.795087] Bluetooth: BNEP (Ethernet Emulation) ver 1.3
[   12.795089] Bluetooth: BNEP filters: protocol multicast
[   12.795093] Bluetooth: BNEP socket layer initialized
[   12.797933] Bluetooth: RFCOMM TTY layer initialized
[   12.797939] Bluetooth: RFCOMM socket layer initialized
[   12.797943] Bluetooth: RFCOMM ver 1.11
[   13.380033] Bluetooth: hci0 command 0xfc05 tx timeout
[   21.376079] Bluetooth: hci0: Reading Intel version information failed (-110)

And, this is the output of rfkill list all:

0: hci0: Bluetooth
        Soft blocked: no
        Hard blocked: no
1: phy0: Wireless LAN
        Soft blocked: no
        Hard blocked: no

Recent Developments

When I wrote this question, I could use the Intel 8260's Bluetooth with no problems whatsoever, if I booted into Windows.

But today, Bluetooth has stopped working on Windows as well. The Windows Device Manager indicates that the device has a power failure.

I did leave my desktop powerd on for two days straight, with Ubuntu running. Maybe that might have damanged this device -- the prolonged period of not being detected, and not being managed properly by the kernel/OS?

Intel 8260 Power Failure

Any help would be greatly appreciated!

The issue has been resolved by Intel recently !
Windows drivers where somehow interfering with the device firmware.
Just follow those instructions, from Windows :

Download Intel latest drivers for Windows
Disconnect your computer from Internet to prevent drivers getting installed via Windows update
Uninstall your current driver on Windows through device manager and check "delete local driver"
Shutdown Windows
Boot Windows (don't forget, must have no internet access)
You should see “Unknown device” in device manager on reboot
Install the latest driver previously downloaded
Boot to Linux
Boot to Windows
[optional, if anything wrong happen] Dump the content of HKLM\System\Software\Intel\Bluetooth key contents to a text file immediately after any issue occurred

Resetting the BIOS CMOS seems to be the only fix for this problem for now. This solution was described in this Arch Linux thread, which chili555 pointed me to.

Linux picked up the device again after I reset my motherboard's CMOS (by taking out the battery for a couple of minutes). I did not boot back into Windows after that.

P.S. The power failure screenshot above is unrelated, and was caused by a lose internal USB connection going into the Wifi+Bluetooth PCI-E chip.