The thing is I have now pulled out my N900 and found that has also lost all the Skype contacts. Surely the issue can't be both devices? I see others have had this problem on both devices so something must be wrong somewhere. There was a Skype update sometime around the time the issue first arose.