Showing contact name with received SMS from Google Contacts
My iPhone contacts are synced with Google Contacts (using an Exchange-type connection; the regular one didn't work) and I had a similar issue, for which I stumbled on the following information by carefully comparing the contact lists.

Contact items (phone, address, etc.) on both platforms are tagged with a label, typically displayed to the left of the phone number or whatnot (in blue on the iPhone). As far as I can tell, if the Google contact has a label the iPhone doesn't use, the syncing protocol won't pick up that number, and the iPhone won't get it as part of its internal database of contacts. Likewise, if you add a phone number on the iPhone with a label that isn't on Google's prebuilt list, then it won't get synced back to Google.

The iPhone will put a name on any incoming or outgoing call for which it can find a phone number, but if the phone number doesn't make it into the phone because it was lost in the syncing process, then it can't display it.

The easiest solution for me was to relabel phone numbers and addresses with the useful common labels "Home", "Work", and "Mobile". There are other idiosyncrasies, but it's way too much detail for this answer, especially since I don't know what the sync code looks like and therefore can't give an authoritative description.