This is a real issue. Even moving from my iPhone 4 to the iPhone 5c I ran into a few issue. My apps were all backed up on iCloud, no issue there, or so I thought.
While restoring from iCloud I was told that some apps could not be restore because they were no longer available on the app store. Huh? What's the point of backing up to iCloud if you cannot restore everything that was on your previous device directly from the backup?
