Just found this thread. I've had TWO fails of my Logitech Bluetooth MX5500 Mouse/Keyboard combo under Win 8.1 since I upgraded. NEVER has this happen on the older OS's on this computer, Vista and W7 (all are 64 bit).
This first time it happened was about 3 weeks ago. I was using the mouse and all of a sudden it stopped working. So I just used the power button to re-boot the computer and it was working OK. Thought it was a glitch.
Last week, when the computer powered up, no mouse nor keyboard (keyboard said NO CONNECTION in its display). I tried to re-connect the mouse and keyboard but it didn't work using the button on the dongle and the mouse and keyboard. I then pulled the USB dongle and heard the familiar 'ding' when USB devices are plugged in or removed. Since this was on a USB port on the back and hard to reach, I placed the dongle on my display that has a USB port. Immediately the device was recognized and re-connected.
Has NOT occurred since.
I've reported this on the Logitech forum too and no answer. I was wondering if I had/have a h/w problem, either the USB port or possibly the dongle? It could be within W8.1 too. I've got some stand-alone DVD's and I've booted those, mouse and keyboard does work with them.
Right now, I'm leaning towards a W8.1 problem.