The BT pairing process can be temperamental. If it's a 2005 E46, the device must be paired within 2 minutes of turning the key (instead of a pairing button, the system stays in auto-pairing mode for 2 minutes). I also could only pair my when the key was turned to accessory, instead of on.
Have you gotten far enough along in the process to be prompted for the passkey?