Purtroppo il tuo mi sembra un caso alquanto singolare.. ..può essere che ci sia qualche App installata che disturba!
Sopratutto se hai già fatto i WIPE della Dalvik e della Cache..
Figurati che io ho rimesso le App con MyBackup Pro e mi ha anche ripristinato i collegamenti per gli aggiornamenti al Market e ciò senza alcun problema.