First, don't waste your time trying to "repair permissions." That feature, which was always useless, has finally been eliminated from OS X.
Please take each of the following steps that you haven't already tried.
Step 1
You may need to synchronize contacts between the Mac and your other devices. One way to do that is via iCloud. On the Mac, open the iCloud preference pane and sign in if you haven't already done so. Check the box marked Contacts. Do the equivalent on your mobile device(s).
Make sure that your contact accounts are enabled in the Accounts tab of the Contacts preferences window.
Step 2
From the menu bar, select
▹ System Preferences... ▹ Language & Region
From the Region menu in the window, select one of the preset regions. If one is already selected, choose a different one, then change it back. Close the preference pane. Quit and relaunch Messages.
If you still have the problem after taking those steps, post your results.