Che ci sia qualcosa che non va ormai è fuor di dubbio.
Il problema è proprio capire cosa, diminuendo i parametri in gioco.
Le applicazioni acquistate, se ne hai, rimangono nel tuo account del market.
Le altre devi riinstallarle una ad una, sempre dal market.
Io uso AppBak per farne la lista sul telefono e poi usarla per riinstallare tutte le app.
Ci sono anche altri metodi meno certosini (installazione da recovery), ma ti complichi la vita e in questo momento forse non ne hai bisogno. Visto che richiedono root, kernel, ecc...
Lo so che è una scocciatura. Valuta tu se valga la pena...