Phone Firmware Nokia Bluetooth Phones: Firmware updates often required!
Several Nokia phones require firmware updates before they will support Bluetooth correctly. You can check your firmware revision by typing *#0000# on the phone's keypad.
Minimum required firmware versions
Nokia 6310i: 5.50
Nokia 6230: 3.15
You can take your phone to a Nokia licensed repair shop and they will update the firmware for you for free as long as the phone is still within its Nokia warranty period.
Be warned that I know of at least 1 case where a firmware update has caused the loss of all personalised information stored on the phone. I strongly advise that you make a copy of any important data from your phone before having it updated.