I had a problem where my headset was not being recognised a while back too. I remembered from another old Nokia handset that headset profiles are stored in with the handset profiles so editing a profile might influence it.

And it did. I cannot remember if I simply changed profiles from 'general' to 'silent' or if I actually edited a profile and tinkered as well, but this solved my problem. I hope it works for you too.