In our post on compatibility we explained how Bluetooth LE connection problems are more likely to be with Android rather than the devices (beacons) with which they are communicating.
If you are experiencing such problems you can try clearing your Android Bluetooth cache:
Settings
Select Application Manager
Display system apps (swipe left/right or choose from the menu in the top right corner)
Select Bluetooth
Select Storage
Tap Clear Cache
Restart the phone
Note that these menus are not available on the latest versions of (vanilla, non-OEM) Android because Google has unhelpfully removed access to system apps.