Also meine in Mac OS X integrierte Bluetooth-Software funktioniert einwandfrei, ich weiß gar nicht was du hast.
Schonmal andere Programme ausprobiert? Oder Handy ausgeschaltet?
Ich denke mal nicht, dass das Handy das Problem darstellt, eher der PC oder sogar nur die Software. Vielleicht blieben Daten bei der Deinstallation hängen, die das Problem verursachen? Dazu mal mit RegCleaner (Download) durchschauen.