Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I had the same problem with my PB. What I did was keep hitting the keys while it's trying to pair up with. I really don't know if that really works or not but that's what I did and it works fine now.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.