I have been having problems with my contacts on my phone, I would create a new contact and it doesn't sync with iCloud even though all my settings are on correctly. As a result on messages on my mac it just shows the number not contact...
You didn't ask here...how did you determine that all of your settings are correct?
If there aren't any settings issues I'd be looking for a network issue...but first I'd really look at the settings again because, in my experience with my own thinking, I'm usually wrong when there's a problem and I think I've eliminated a setup issue.