update: I had a call from Nokia.

They suggested a Hard Reset.

Has anyone got any experience with doing these? The chap I spoke to said I would lose everything including data stored on the mass storage. So I guess there is no point using the phone to backup my contacts etc?

I would have to use Nokia Link, which is only in Beta for Windows XP.