This is most likely a threading issue. I ran into a very similar issue with BLE on Samsung Galaxy S4 devices. It appears that Samsung's implementation of Android handles BLE differently than others (Nexus 7 device worked fine). Albeit, you must explicitly run your BLE connectGatt method from the UI thread. Here is an example:
// Create handler for main thread where mContext is application context
mHandler = new Handler(mContext.getMainLooper());
...
// Connect to BLE device from mHandler
mHandler.post(new Runnable() {
@Override
public void run() {
mBTGatt = mBTDevice.connectGatt(mContext, false, mGattCallback);
}
});