Disclaimer: This obviously may not work for everyone but it did for me. These are all assumptions..
Assumed Issue: During the operating system upgrade, the device lost its hooks to the some types of data on the device (i.e. music files, movies, etc.). So all that other data on your device was a bunch of your old data just unrecognized by your device. Assumption: NOTHING TO DUE WITH iCLOUD but more just the upgrade of the operating and file system on the device.
My Devices:
iPhone 4 (32GB) (Latest iOS 4 version before trying to upgrade to iOS 5)
Windows 7 Premium
My appearance:
~15GB music
~5GB video
~2GB apps
~1GB photos
~and the dreaded 20 GB of "Other"
Sum: More than she can handle
My resolution:
1) Perform backup of mobile device in iTunes (I did this before unchecking all the types of media to Sync to mobile device in iTunes)
2) On mobile device, go to Settings->General->Reset->Erase All Content and Settings
3) When this has finished, back in iTunes, perform a restore from the backup.
Consclusion
I believe this re-established all the hooks to my music and video data from my PC to my device and resynced all my apps, music, videos.
If I happen to lose all my data from my apps oh well, I guess I'll just have more Angry Birds levels to master... :-P