It may take 30 or more seconds for the Pair notification on certain Android devices (Motorola, LG, HTC, Sony) to display. Open the notification, tap Pair. This should establish the Bluetooth connection.