Hopefully you found your solution already, but just in case....
I just bought one and it took me a while to figure out how to pair up. I'm running stock on a Thunderbolt. I wasn't holding the talk button down long enough, the red/blue flashes are very fast, not the slower flashing. I had to open the phone screen and "dial" 00000. Incredible sound but limited voice commands. I'll play with it some more, maybe I'll do better.