Sí, se pierde todo.
Yo como tengo mis contactos sincronizados a GMail no hice ningun Backup, cuando tuve el movil nuevamente operativo sincronice y todo volvió a su sitio. Además como utilice otra MicroSD que la que tengo puesta, tampoco perdí las fotos o la música, ni siquiera los tonos que metí, todo sigue en su sitio salvo el registro de llamadas, SMS y cosas similares.
Los programas del market al estar asociados a tu cuenta de GMail tan pronto como sincronizas se empiezan a descargar a saco, pero los que hayas instalado por tu cuenta tendrás que reinstalar.
Saludos