Yo opté por la solución más drástica.
Mybackup de todo excepto de los contactos. Arrancar en Recovery. Hacer wipe. Reboot
Arrancar de nuevo todo y recuperar los backup (sin contactos)
Salu2
P.D. Se supone que tus contactos los mantienes en Gmail. ¿lo has comprobado?. Si también los has perdido, creo recordar que hay una apli (contacts2sim?? o algo así) que te pasa de contactos de memoria a la sim. Manéjate por esos campos que ahí estará la solución.
Si tus contactos los tienes en Gmail, no te preocupes, que se sincronizarán solitos después del wipe