Try this
"I recovered my contacts by doing the following. Clicked on Tools, Options, Privacy. Right Click on Entries in the Allow List that you wish to recover. Click on Add to Contacts. They went straight back onto the list without having to contact the person. Grouping and Nicknames had been lost. Not sure if it helps everyone here or not."
otherwise, from what i can make out this is a very common issue with version 9
go back to your previous version if the above does not help.
until ms fix the issue