Bluetooth in Toshiba Satellite C845

Similar problems were reported last year here (kernel 4.1.1: Bluetooth: hci0: Failed to load rtl_bt/rtl8723b_fw.bin) on Ubuntu forums.

Summary of steps to solve it there (which you probably shouldn't use!):

sudo dpkg -i  linux-firmware_1.145_all.deb
sudo updatedb
rfkill list all; hciconfig -a

Updated steps for your Ubuntu 15.10 on the other hand would be:

sudo apt update
sudo apt install linux_firmware
rfkill list all; hciconfig -a

This is based on instructions for 15.10 found here (https://www.howtoinstall.co/en/ubuntu/wily/linux-firmware)

Additional information that may prove helpful can be found here (Bluetooth not detecting any devices) where Pilot6 wrote an answer for an rtl8723au-bt driver.

As far as Toshiba's suitability for Linux... historically it has been very good however recently I've read comments some new machines are Windows only. In this case however it's more a reflection of RealTek / Broadcom hardware installed inside which Dell's could also have. Either manufacturer could also have Intel hardware WiFi / Bluetooth as well though.

FTR I have a Dell Laptop with Intel inside and haven't had any real bluetooth problems to date (fingers crossed). Hopefully your problems get solved soon!

A local AskUbuntu user, Pilot6, provided a PPA (ppa:hanipouspilot/rtlwifi) containing the required drivers to ensure that the RTL8723 chipset works with your machine.

Essentially, you need to add this PPA to your system:

sudo add-apt-repository ppa:hanipouspilot/rtlwifi && sudo apt update

Next, install the appropriate DKMS modules and drivers to your system:

sudo apt install rtlwifi-new-dkms linux-firmware rtl8723au-bt-dkms

These two commands (combined) will install the required drivers to your system and kernel. Additionally, this will work after any kernel update, due to the nature of DKMS.

Furthermore, you are also installing linux-firmware, which allows for some (better) firmware support for similarly quirky devices.

If you would rather compile from source, you can see this answer, which also includes (further) PPA information. Alternatively, if you want DKMS support, check here.