Z600 and bluetooth headset keep losing each other

Hi - I hope somebody can help
I have a Z600 Sony Ericsson - bought new unlocked about 18 mths ago, always
worked really well. I have a Logitech HS01 headset, bought new about 6
months ago, which I had no problem with until about a week ago.

What I find now is that everytime I switch the headset on, the phone fails
to connect. I have to delete the device on the phone, then find it again.
The phone usually fails to find it half a dozen times, then suddenly finds
it and everything works okay.

The trouble is this is all happening when I'm driving and it's both
dangerous and annoying.

My question is - is the problem with the phone or the headset? I would love
to do a "warm reboot" on my phone but don't know how to and the manual is
very unhelpful. If anybody knows how to sort this out, I would be really
greatful.

Many thanks
Caaagh