Android phone lost, what data can I get onto new phone? Sorry about the clumsy question.

My Android HTC Magic was lost/stolen last night. I had an unlock swipe code, power-on SIM code and have called the phone company and had it blocked, so not too concerned about the phone itself being used by someone else.

What I am thinking about is when I get a new phone, what data/info can I get back easily as I can't just copy it from the old phone now? Obviously GMail/Contacts/Calendar are all stored on the web, any purchased apps are linked to my Market login, and I'm not concerned about photos, music etc that were on the SD card.

What I'm more concerned about are my preferences, settings, SMS texts, list of installed apps, prefs, data from those apps, etc. Are those all gone?

Addendum: I was thinking of rooting the phone, so did take a standard Nandroid backup a week ago that I have a copy of on my PC, if I get an identical model of phone and restore that, will my data come back? Also what happens if I try to restore that onto a different model of phone (I'm assuming bad things would happen)?
As long as you didn't turn these features off, simply adding the same Google account you used on the old phone to the new phone will restore a lot of your data.

Backed up: 


Google Contacts
Installed apps  
Wi-Fi settings  
Bluetooth settings  
Purchased apps  


Not backed up:  


Sim-only contacts
Preferences  
Settings  
Texts  
Application data


To answer your second question: the Nandroid restore should work on an identical phone. However, this will not work for a different phone unless you only copied data in the backup. Any system data will cause problems on a non-identical device.