Mine started working again after a hard reset or Reset All Settings, not sure which one.
----------
If you ever do a Restore as New, any photo older than 30 days (I think) will disappear. I think it has to do with the limitations Apple has on Photo Stream. If I remember correctly when Steve Jobs introduced iCloud he said there was a 30 day/1000 photo limit.