The key is to do everything from the BJII.

1. Turn on BT on BJII
2. Setup "Discovery on/Visibility on" on your PC/Laptop.
3. Back to BJII, BT->Add new device. It should find your PC/Laptop and ask for pairing key.
4. Back to PC, enter the same paring key. When asked, allow the device(BJII) to use ActiveSync(Always).
5. Back to BJII, Start ActiveSync. Menu->Connection vis Bluetooth.
6. PC should say it was connected to BJII via ActiveSync.

PS: I used Lenovo T61p supplied bluetooth driver stack. Never tried with default Microsoft BT stack.