Go into device Settings/Wireless and network/Bluetooth settings....
Tap and hold on the bluetooth device, select Unpair, then go thru the pairing again. This should work. If not, do a Factory reset (hard reset) to dump the device memory by booting into recovery mode and select Wipe data/factory reset.
Backup your data first. Any system update should be followed by a factory reset to remove any residual files the update didn't remove.....