Como dice @
raziel-77 los contactos se guardan en google, nunca los pierdes, tambien puedes usar My Backup Pro (gratis y de pago) para mi es mas comodo el My Backup que el Titanium, pero eso ya va por gustos...
Con ambos puedes hacer bakcup's de apps, contactos, sms, mms....
Saludos!