I have an IBM T42 with built in bluetooth and was able to connect and sync without any problem.

I have also been able to connect the Blackjack to my iBook and sync using MissingSync.

The only thing I may have done different is that initiated everything from the phone and not the laptop. Try clearing the partnerships and then going into the ActiveSync program on the phone and select connect via bluetooth. Follow the promts to setup the partnership and to sync the phone.