I've been struggling this problem for a good few months now and periodically try and tackle it doing the usual thing of turning iCloud off and on again, turning Contact syncing off and on again, looking for the old location preference. Nothing was working.
I just tried again using some of the new info on here and have managed to fix it. The trouble is, I did so many things I'm not sure which one did the job! I'm using the latest general release versions of macOS and iOS (10.13 and 11.0.1).
Here's what I did:
1. I signed out of everything on my Mac. iClound in Sys Prefs. FaceTime (I noticed this was signed in using an old email address and the location was set to USA. It could be a clue – have you recently changed your email address and still logged in). Messages. iTunes (also deactivating all my old machines).
2. I signed out of iCloud on my phone.
3. I logged into icloud.com and signed out of all browsers.
4. I logged into appleid.apple.com and removed all my devices.
5. I also changed my email address. I was using a Gmail address with
+appleid@gmail.com in it to differentiate it from other services. To make sure the + wasn't causing issues I removed the +appleid (so it was just my regular gmail.com address).
6. I restarted my Mac and phone.
7. When my Mac started up I signed into iCloud in Sys Prefs.
8. I opened FaceTime and noticed I was already signed in (location was again set to USA so I changed it to UK)
9. I opened Messages and the first thing I noticed was the names were all displayed corrctly.
10. I signed into iCloud and the names were still there (phew!)
11. I noticed my mobile number wasn't yet assigned to my account so I logged into iCloud on my phone
12. I was then prompted to use my mobile number on the Mac, which I accepted and the names are still displayed correctly.
I'll let you know if it slips back to the old behaviour at all, but I suspect the problem is that there are conflicting locations coming from various devices.
Looking forward to seeing if this works for anyone else