Basically, last night I had a blinking update sign on my N900. I clicked to update as I normally do. The update was 100% successful (Before this, my last update was on 20th April 2010).
As the phone re-booted itself I checked my messages and found that all my new messages have vanished from my Conversations & recently added contacts between 20th April - 28th May (last night)!!! ;0(
I contacted Nokia and they said there is a way to retrieve these but when I took it to a Nokia Centre (in Carphone Warehouse) they said they will need to reboot the whole thing and everything will be deleted!