Yo siempre con Nokia tenía problemas con Outlook ya que no aparecian bien los teléfonos en contactos.
Una pregunta. El número de tlf. en contactos en que pestaña lo tienes. Pude ser que si lo pones en la pestaña de "movil" al sincronizar te funcione.
Si esto es asi y tienes muchos contactos puedes exportar el fichero de contactos a un *.xls, modificar ahi los teléfonos y después volver a importar.
Ya me contarás como te va
Saludos