The standard first attempt at "fixing" BT problems is to do a smc and pram reset (try these first). But for mac pro's, if you are using a magic mouse say, about 3 or more feet, from the mac pro, you are most likely in for some continued aggravation. That's because the BT antenna is hidden in the back of the mac pro (faraday cage) and the magic mouse BT, for lack of better words, $ucks.
Here's a thread on this subject:
Basically it comes down to wiring your own external antenna in place of the internal one already there or using a BT USB dongle. I use a dongle myself on my 2010 mac pro.
Well that another basic attempt at trying to get BT back.
Then there's the ultimate "sledge hammer" of doing a full factory reset of BT but that requires XCode. I haven't been posting that any more because (a) requires XCode and (b) for Lion users it is a bit harder to get and they have to pay a small fee for it.