Welcome to Android Central! This happens even with numbers that are in your Contacts list? Are the numbers exactly as they're saved in your Contacts? Even a tiny difference like the presence or absence of a country code can make it not recognize the contact.
Also, go to Settings>Apps, select the Phone app, and make sure it has Contacts permission.