Los contactos no los tenías sincronizados en gmail? Así no los pierdes... O también los puedes poner en la sim...
Programas como el recuva te pueden intentar recuperar archivos sueltos como música, fotos, vídeos... pero de resto... no creo que puedas recuperar nada más y por supuesto, no te recupera todos.
Podrías salvar los contactos si en algún momento exportaste una copia de los contactos a la sd externa y da la casualidad de que ese fichero es una de los que te recupera el programa.
Suerte.
