Cannot Pair Bluetooth Headset with Nokia 5230

What headset is it? Are you sure you checked all the settings on your phone?

which headset r u using...if its nokia bluetooth headset...just long press the power button untill the light start blinking...then try to detect it.
It had to be done each time u want to pair it to any mobile

Mine is a local chinese made A2DP one (bought from deal extreme) and my roomie's is a original nokia one (single ear) he had got with his 5800.
I am 100% sure there is no problem with the headsets. I have a sony ericsson w800i and it perfectly pairs with both these headsets.
I think i read somewhere that there is problem with pairing of BT headset with some symbian phones.

So what are you doing on Symbian to pair it? Walk us through the steps, and maybe we can tell you what's going wrong.

I am doing this on my 5230

1. Go to connectivity and turn the bluetooth ON
2. There i am trying to add a new paired device and it fails to detect my headset.

Also going to settings -> Phone settings -> accessories does not have any mention of BT headset.

ur headset is locked with ur SE mobile.....just try once what I say even if it seems dumb
try to reset ur headset by either long pressing the powerbutton...or find any other point to reset the headset....then try to detect with ur nokia mobile

it will work for sure