The issue actually is due to incomplete Bluetooth 4.0 Attribute Protocol (ATT) implementation in BlueZ stack. Starting Android 5.0, the way it's retrieving GATT characteristics and services is a little bit different. Specifically it is using 'Read By Group Type Request' (Core_v4.1 Bluetooth Specification, section 3.4.4.9) which seems not to be correctly implemented in BlueZ. IIRC it was specifically due to Android 5.0 using multiple ACL packets to form one request. iOS and earlier Android versions used one ACL packet for one request.
UPDATE!!!
The 'BR/EDR not supported' bit in the advertisement (bit 2) should be specifically set, or the stack(with broadcomm dongle in my case) will use BR/EDR and BTLE. The workaround is changing the leading advertisement package from 020102 to 020106
btmgmt le on
btmgmt bredr off
Use btmgmt for configuring the adv hcix:
btmgmt -i hci0 power off
btmgmt -i hci0 le on # Enable LE
btmgmt -i hci0 connectable on
btmgmt -i hci0 bredr off # Disable BR/EDR
btmgmt -i hci0 advertising on
btmgmt -i hci0 power on