We had a few users report this issue.  We were able to determine that it was caused by an update in our HR system that temporarily disabled their Salesforce user accounts.  We were able to reproduce it in our partial sandbox....users that had favorites no longer had them after deactivating and then reactivating their profiles.  Adding more favorites and repeating the exercise also resulted in the favorites being removed.