I have just got Bluetooth working on my Thinkpad (Debian Testing/Squeeze) and it will pair with my Android 'phone but the signal keeps fluctuating. The link quality between 100% and -1%, the strength between 58% and -1 and it does this at around 2-5 second intervals.
It does it even when the 'phone is next to the laptop. Can anyone suggest a reason for this?