messages display phone number rather that contact name

[AC Question]

Since the most recent security patch to 6.0.1, messenger no longer displays the contact name just the phone number. Contacts do appear in the Contacts app. The contacts are syncing from Office 365.

I've tried deleting the cache partition. Unfortunately that did not help.

I did notice that updating a contact in O365 will cause the next message from that person to be properly identified in the Messenger app. It seems like there should be a way to fix this on the phone rather than modifying a couple thousand contacts.

Any suggestions?