As many 6310i users (including myself) found out, Nokia decided to be very nice, and only support their own headsets/headset profiles. However, after doing some research and over an hour of talking to a Nokia tech on the phone here is what i found:
First of all, type in *#0000# to find the current firmware you are using on your phone. In my case it was 4.xx (dont remember exactly). The latest firmware for nokias is 5.51 i believe. Since the 5.50 version, the BT support has been MUCH better as i found out from both the tech and countless web-sites that i went to verify this (however some users still reported inability to connect through a headset profile). If you cant add the headset profile, you almost certainly have 4.x firmware on your phone though. To get it upgraded check the nokia site for your local shop that can do it (most cant, they just send it in to nokia to get updated, which takes 1~2 weeks). This service is free if it is covered by your warranty still, if not you pay for shipping. Also dont forget that you will loose all your data when you upgrade the firmware, so back it up first!
I'm about to send off my phone to get it updated, so I'll keep you updated on the status when it gets back.