I too was having problems with BT pairing on all my devices after Lion update - here's how to fix- shut down your computer, power up and immediatly hold cmd option "r" and "p" (all at the same time) your screen will flash a few times but you want to keep holding the buttons through two cycles of start-up. Release the keys after the second start-up. Then re- pair your BT device and it will work.
I had to do this on my macbook air and mac mini. On the Mac Mini - the system restarted said it was recovering from internet, once it was done all my BT devices worked just fine.