As more and more companies adopt a hybrid approach to Office 365 there is an increasing mix of on-premises and online users, but not all policies applied on-premises will carry over to Office 365 as gracefully as you might hope.
As an example, consider an organization that has determined tha users with both a Mac and PC couldn't possibly have the need to update their contact list from a Mac client so they've enabled the Unified Contact Store (UCS). For the nerds, this means that:
Set-CsUserServicesPolicy -Identity Global -UcsAllowed $true
Now consider that user has signed in on a PC and successfully migrated their contact list to UCS at some point. And that same user later migrates to Skype for Business Online where the global UcsAllowed paramater is set to $false by default.
The end result is the user will find they are unable to have changes persist to their contact list. The Skype for Business client honors new additions or changes to group membership within the UI during that session, but those modifications will be removed on the next sign-in or registration refresh. If the user adds a contact, moves them to another group, or removes them from the contact list, the original contact list will be reset on the next registration attempt.
On the other hand, this is a really nice trick to play on someone if you want to make them think they've lost their mind.
The issue here is that the user was previously using UCS, but Office 365 does not allow for this feature by default. When the user signs in UCS kicks in to provide the contact list, but changes are only being saved against the Skype for Business Server because the policy prevents UCS.
In order to resolve the situation you'll need to roll the user back to using the Skype for Business Server contact list provider option via:
Invoke-CsUcsRollBack -Identity [username]
This will force the user to immediately sign out, but will start using the Skype for Business Server as the contact list provider on the next sign-in.