Los contactos se guardan en la cuenta de Google. Como el calendario y algunos de los últimos SMS también (creía que guardaba todos y te aseguro que no lo hace grr)
Si te manejas en linux hay un comando dd con el cual puedes hacer una especie de imagen de la sd y copiarla en la nueva.