Make sure you have the area code stored for the contact.
The safest bet is to delete that contact's phone number (but not the contact), have that person call you, then choose Assign to Existing Contact or words to that effect. That ensures the number is stored the way the carrier transmits it. This is the most frequent issue for our customers.