Android phone lost, what data can I get onto new phone?
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.