Mis contactos del iPhone están sincronizados con los contactos de Google (utilizando una conexión de tipo Exchange; la normal no funcionó) y tuve un problema similar, para el que me topé con la siguiente información comparando cuidadosamente las listas de contactos.
Los elementos de contacto (teléfono, dirección, etc.) en ambas plataformas se etiquetan con una etiqueta, que suele aparecer a la izquierda del número de teléfono o lo que sea (en azul en el iPhone). Por lo que sé, si el contacto de Google tiene una etiqueta que el iPhone no utiliza, el protocolo de sincronización no recogerá ese número y el iPhone no lo recibirá como parte de su base de datos interna de contactos. Del mismo modo, si añades un número de teléfono en el iPhone con una etiqueta que no está en la lista predefinida de Google, no se sincronizará con Google.
El iPhone pondrá un nombre en cualquier llamada entrante o saliente para la que pueda encontrar un número de teléfono, pero si el número de teléfono no llega al teléfono porque se perdió en el proceso de sincronización, entonces no puede mostrarlo.
La solución más fácil para mí fue reetiquetar los números de teléfono y las direcciones con las útiles etiquetas comunes "Casa", "Trabajo" y "Móvil". Hay otras idiosincrasias, pero son demasiados detalles para esta respuesta, especialmente porque no sé cómo es el código de sincronización y, por tanto, no puedo dar una descripción autorizada.