Hey could you tell me how u resolved the issue with the bluetooth not pairing? I'm having the same issue after the gingerbread update, ur info would really be greatly appreciated, having my bluetooth is a must.
I had to remove the headset from the phone entirely (turn on bluetooth, then menu>settings>wireless&networks>bluetooth settings>press and hold the device and a menu comes up and you can delete it) and then scan for and re-add it to the phone again. Now it pairs up and works great.
I've only had the shift (my first android phone) for about a week, but I had the same problem and the solution for me was simply to to tap on it once it said "Paired but not connected."