Lo mejor con el tema de contactos es tenerlos todos en la cuenta de gmail, así cada vez que cambies de móvil y metas tu cuenta, automáticamente reaparecerán todos tus contactos. Puedes mirar si te permite exportar al gmail los números del registro de llamadas.
Un saludo