RN-41 Not pairing

I am trying to set up a RN-41 module to communicate to an android phone. I am connecting very basic interface: Vdd, Gnd, Tx, Rx to an msp430. Once the module receives power, the phone is able to see it. But it is not able to pair with it. Is there something else that I need to do to make it work?

Any help will be deeply appreciated

Thanks

I discovered last night that pairing my Mac with a Bluesmirf connected to an Arduino UNO required that I that specify the “No password” option in order to pair the two devices. Have you played with the password settings?