I don't know how widespread this is, but it happened to us despite having a robust backup ...
I just migrated my son from a 3GS to an iPhone 4 running iOS 5.01. I wiped the iPhone 4, reactivated it, then restored from a complete backup of his 3GS. His Harry Potter Lego saved game setttings were not preserved. He was, understandably, disappointed. I haven't evaluated his other games. In general iOS 5 migrations have been difficult, with more than expected work to reinstall apps, delete crashing apps and resume them, and restore accounts.
I suspect the problem is some combination of ...
- a bug (of course), perhaps related to Apple's confused identity management infrastructure (Cloud ID, AppleID, StoreID)
- a change in how applications are allowed to store data. If an app is not updated prior to updating, and the app stored data in a fashion that's no longer supported, then data will be lost.
I've moved three users from iOS 3 or iOS 4 to iOS 5, and it's been painful each time. Most credentials have to be recreated. ActiveSync account migration doesn't work at all; accounts have to deleted and recreated. Migrating Google Authenticator was particularly difficult (that's Google's fault though). Worst of all, for my son, is this data loss.
I don't know if Apple will fix this, but I recommend waiting for iOS 5.1 if there's no driving necessity to upgrade to iOS 5.