In his Android Pro-tips talk, Reto Meier (tech lead on the Android Developer Relations team) recommends generating a random UUID and saving it in your app's SharedPreferences. The Android BackupManager will backup SharedPreferences in the Google cloud. If the user restores their user profile from the BackupManager to a new phone, their UUID will be preserved.

http://blog.radioactiveyak.com/2011/05/android-protips-where...