Unable to pair Bluetooth HC-06 to Android device

I have a brand-new HC-06 on a JY-MCU backboard. Right out the box, I had no problem pairing it with my Android phone (LED stopped blinking). When I tried to upload some basic test code, I got a serial conflict and had to unplug the HC-06 to complete the upload. Since then, I have not been able to get the HC-06 to recognize the pairing. My phone has no problem pairing, the module shows in the BT list and will challenge for and accept the passcode. However, the LED will not go solid to indicate that the module has paired.
Any suggestions? I've reset everything to the factory state as best as I can, but to no avail.

I can't identify the problem but it is probably something stupid that will only happen once. At least you are using hardware serial and recognise that the HC-06 will clash if connected while uploading.

Here is some background that might be useful

http://homepages.ihug.com.au/~npyner/Arduino/GUIDE_2BT.pdf
http://homepages.ihug.com.au/~npyner/Arduino/BT_2_WAY.ino

Thanks, that's actually the exact document I was using to try and get this working in the first place...
I was able to replace the HC-06, but the new one does the exact same thing, only this one didn't even pair once. It's gotta be something between the module and Android, so I guess it's off to Android forums...
Thanks anyway!

I'm hesitant to raise this, but it might forearm you for the Android Forum:

You will see in my notes that I started out using an HC-06 but despaired of ever getting my tablet to work. This to the point where it was a principle reason for getting the phone, which was fine. I found out by accident that the tablet DID work with an HC-05 - just as if nothing had ever been a problem.

I blamed the tablet. From what you are saying, I could be wrong.

You might find that replacing the HC-06 with an HC-05 will fix the problem - and I would be very interested to hear about that!