Estás en lo correcto.
Al cambiar la tarjeta tienes que hacer nuevamente todo el proceso de flasheo.
Sí, los contactos están guardados en la nube y se autosincronizan, tal y como puedes comprobar aquí
http://www.google.com/contacts
Recuerda hacer copia de seguridad de lo que creas conveniente!