BT Mouse won't connect (unless connected first)

I connected a Logitech BT Adapter (audio receiver) via bluetooth; it works. I then try to connect my BluetoothMouse3600 Microsoft Bluetooth mouse and it takes ~20 attempts to connect, and then if I'm lucky it'll work for a few minutes on the 20th attempt, before it fails.

The mouse would show up in xinput and look fine, but the cursor wouldn't move - except that one attempt in 20 which would connect and work but fail after a few minutes (at which point the mouse will have changed to "off" in the BT menu, despite me not turning it off; turning it on does nothing and the reconnect attempts continued.

I tested this with an intel 7265 and an 8260 in the same laptop (HP x360 4109NA) and it's the same. Lot's of rebooting and manually connecting reconnecting with bluetoothctl and it refused to work.

I finally realised that the only way to make the mouse work is to disconnect the Logitech adapter and mouse so nothing is connected via bluetooth, then connect the mouse, and once the mouse is working connect the Logitech BT adapter. Then all the problems go away and I'm happy.

I don't know if it's related (or if it's a bug in bluez or something else or if it's the way microsoft made the mouse), but the mouse only shows up as "all types" in the GUI, it does not appear in the list of "input devices (mouse, keyboards, etc.)".

ProblemType: Bug
DistroRelease: Ubuntu 16.04
Package: bluez 5.37-0ubuntu5
ProcVersionSignature: Ubuntu 4.4.0-31.50-generic 4.4.13
Uname: Linux 4.4.0-31-generic x86_64
ApportVersion: 2.20.1-0ubuntu2.1
Architecture: amd64
CurrentDesktop: Unity
Date: Wed Jul 20 09:21:33 2016
EcryptfsInUse: Yes
InstallationDate: Installed on 2016-07-15 (4 days ago)
InstallationMedia: Ubuntu 16.04 LTS "Xenial Xerus" - Release amd64 (20160420.1)
InterestingModules: rfcomm bnep btusb bluetooth
MachineType: HP HP Spectre x360 Convertible
ProcKernelCmdLine: BOOT_IMAGE=/boot/vmlinuz-4.4.0-31-generic.efi.signed root=UUID=a664806a-fe18-4869-99aa-7a668bd6c131 ro noprompt quiet splash vt.handoff=7
SourcePackage: bluez
UpgradeStatus: No upgrade log present (probably fresh install)
dmi.bios.date: 06/22/2016
dmi.bios.vendor: American Megatrends Inc.
dmi.bios.version: F.42
dmi.board.asset.tag: Base Board Asset Tag
dmi.board.name: 804F
dmi.board.vendor: HP
dmi.board.version: 33.76
dmi.chassis.type: 10
dmi.chassis.vendor: HP
dmi.chassis.version: Chassis Version
dmi.modalias: dmi:bvnAmericanMegatrendsInc.:bvrF.42:bd06/22/2016:svnHP:pnHPSpectrex360Convertible:pvr:rvnHP:rn804F:rvr33.76:cvnHP:ct10:cvrChassisVersion:
dmi.product.name: HP Spectre x360 Convertible
dmi.sys.vendor: HP
hciconfig:
 hci0: Type: BR/EDR Bus: USB
  BD Address: A4:34:D9:D4:47:65 ACL MTU: 1021:4 SCO MTU: 96:6
  UP RUNNING PSCAN ISCAN
  RX bytes:6748669 acl:114809 sco:0 events:635424 errors:0
  TX bytes:539612008 acl:631588 sco:0 commands:2876 errors:0