We are also using the PBA31309 in our products and customers are complaining about this issue.
It is a real and pressing problem for us since providing connectivity to Android devices is a core feature in our products.
After ~2 months, we got recognized but it seems Intel is unable/unwilling to fix the issue.
Here is the official response:
This seems to be an incompatibility of the SPP stack with Android 4.3 RFCOMM TS07.10.
As you know, the stack is implemented in ROM and the patch space in the EEPROM is extremely limited for eUinstone PBA31309.
It will be very difficult to get an analysis and a fix from Mecel.
Unfortunately, I do not have Bluetooth Sniffer hardware available and not enough time to test each device against the Bluetooth Standard.
Intel, please provide an updated firmware that is fully TS 07.10 compliant and - if possible - tested against Android 4.3, 4.4, 5.0, 5.1 devices.