There may be problems with Secure Simple Pairing mode (SSP) and
this device. Linux SSP implementation (in the kernel version that
Android uses) has SSP issues, that arise with some devices but
not with others.
A way to test this is the following command (takes a rooted device):
hciconfig hci0 sspmode 0
You can do this even if device is already paired; the SSP pairing
still holds.