Ma te lo fa solo con alcune, o con tutte le applicazioni che provi a scaricare?
Oppure solo con le app disinstallate che provi a reinstallare?
Comunque prova innanzitutto a riavviare, ma lo avrai già fatto, e poi prova a cancellare la cache da recovery, in quanto il file apk che scarichi dal Play Store viene temporaneamente conservato lì, ma poi dovrebbe essere automaticamente eliminato una volta terminata l'installazione. Per qualche motivo la cache potrebbe essersi riempita, a questa si riferisce l'indicazione di memoria insufficiente, non ai 3Gb e rotti di memoria interna.