It's a small World as they say
As to getting Bluetooth to work on any Linux box, it can frustrating. There should not be much difference between Mint and Ubuntu in this regard though.
On Crunchbang it 'just works' once the packages are installed. (although I must launch the systray applet manually using alt+f2 and typing bluetooth-applet)