Bueno, es que ya me pasó una vez con un móvil windows mobile, con 400 contactos duplicados (y menos mal que no borrados jeje)
Si el sistema de gmail interpreta que después de la restauración es la primera vez que sincronizas ese teléfono, puede interpretar que los contactos del tlfno. sean nuevos aunque sean el mismo nombre (se pueden tener varios contactos con el mismo nombre).
La otra posibilidad es que si no restauras los contactos vaya y te los borre porque interprete que ese teléfono ya se había sincronizado y lo que has hecho es borrarlos
Si está bien diseñado no debería pasar ninguno de los dos casos, pero ya se sabe... habría que saber cómo interpreta google el teléfono restaurado.
si alguien lo ha probado agradecería comentarios, también sobre lo de las aplicaciones (si se restauran tal cual)