I have a Motorola H700 bluetooth headset, and it can play up when messing around with connections.
It worked perfectly well with my Nokia E90, but then I tried it with my TomTom Go Live, and then it worked with neither.
(Re)Pairing with the Nokia E90
This is what I did to get it to connect to the E90 again:
1) Delete the pairing in the E90
2) Put the headset on to charge for a minute (this performs some sort of internal reset)
3) Press and hold the call button - the light turns purple
4) Open the boom
5) Release the call button - the purple light remains on
6) Search for the headset from the phone
7) Enter the passcode of '0000'
8) Select 'Yes' I do want to save settings, and I do want to automatically pair.
Note that the headset does have a timeout, so you do need to shake a leg when messing around with the phone.
This operation got the headset working well again with the phone.
Pairing with the TomTom Go Live