A mi me pasaba justamente esto en mi note 1. Tenia instalado un programa, que era para darle mas negro a la pantalla, no se si recordaran los viejos del lugar que el Note 1 tenia unos pixelazos en los fondos de color negro como garbanzos.
Pues bien, no se por que estando esta aplicacion activa, no me dejaba instalar ninguna apk.
Antes de hacer wipes y demas comprueba que no hayas instalado ninguna aplicacion recientemente, y que por absurdo que parezca, sea esta la que te bloquea la instalacion de nuevas aplicaciones.
Saludos!