Thread: "Bluetooth Paired but not connected" error with LG headset

After pairing my Bluetooth headset LG HBM-235 and using it for some time, it stops receiving incoming calls via the bluetooth headset. In the menu settings->wireless & Networks->bluetooth settings, I see the status message "Bluetooth Paired but not connected" message below the device name. I have to touch the device name listed on the screen to make it connect. Most of the time, that works.

I have tried shutting down and restarting both devices - that fixes the issue for some time. But after a few calls, it reverts to the above behavior. As you can guess, doing all this is a major pain for every incoming call. Any ideas how to fix this?