Después de dar muchas vueltas y de volver a instalar un par de veces ICS 4.0.3 desde cero, he llegado a la conclusión que el error en mi caso me lo daba al restaurar el backup que había hecho antes de pasar de GB a ICS. Así que probé a instalar ICS y no restaurar dicha imagen y por el momento me vuelve a funcionar. No entiendo mucho del tema pero creo que puede ser que al restaurar la backup, las aplicaciones que tenias instaladas dan algún tipo de error a Play Store y este no te permite descargar nada. Probablemente sea una tontería lo que haya dicho pero es lo que se me ocurre desde mi total ignorancia del tema. Yo os recomiendo que probéis a no restaurar la backup e intentar descargar algo.