I just solved this problem on my PC and android phone. It was so simple I'm glad to post here in hope this helps everyone.
In my case, under phone contacts I found that phone numbers had been either entered or displayed with ellipses around the area code. For example: any contact in my phone contacts whose phone number was shown in this format (xxx) xxx-xxxx got displayed as a phone number in Phone Link.
When I reentered the phone number in the following format xxx-xxx-xxxx the contacts named displayed properly in Phone Link messages!