Para restaurar backups yo siempre hago wipes cache, dalvik, system. Normalmente los backups No hacen copias de las caches. Por tanto te encuentras con archivos de configuración y binarios restaurados que no corresponden con las caches actuales.
El mejor recovery después de haberlos probado todos es el TWRP, una puta pasada que te ofrece TODO cuanto puedas desear.
http://www.teamw.in/project/twrp2