Usually with BT devices you will press and hold their power button for 3-5 seconds to put them in discoverable mode. Then from BT setup in the phone you would "search for device." As long as the device is in discoverable mode and fully functional, the phone should find it. And .419 had solid BT services, so I doubt it is a phone or OS problem.
Posted from my CrackBerry at wapforums.crackberry.com