After doing some more research, I understand more clearly now.
The photos that were uploaded to My Photo Stream were only kept on iCloud for 30 days. However,a rolling 1000 photos were also kept on your device in the My Photo Stream album, even if they were gone from iCloud. This was separate from your Cameral Roll.
In iOS 8, there is no My Photo Stream album. So when you upgraded, you "lost" all the photos that were in the My Photo Stream album on your device. Only the photos stored in iCloud(the photos from the past 30 days) were synced back later, showing up in your Collections and Recently Added.
That's just plain confusing and dumb. There should have been more explanation on how your photos would be dealt with during the upgrade. Hopefully most people would have had the common sense to back up their photos to their computer.
iCloud pushes all your photos to the My Photo Stream album on your devices and computers, and manages them efficiently, so you don’t run out of storage space.
Your iOS devices keep a rolling collection of your last 1000 photos in the My Photo Stream album. From there, you can browse your recent photos or move the ones you like to your Camera Roll or another album to keep them on your device forever.