When adding contacts between the Moto G 4G (Android 5.1) and the Galaxy Nexus (Android 4.4.4 CM), the Moto G shows a pairing request notification (sometimes twice, presumably once for the incoming connection and once for the outgoing connection). Even if the pairing request is accepted, the connection fails.

This is an intermittent failure - after backing out of the add contact process and retrying, the connection sometimes succeeds.