Desinstala la aplicación de la Store (ponte en el icono y pulsa triángulo y te sale la opción, creo recordar), apaga, vuelve a encender y ve y pulsa el icono de la Store, te la reinstalará y ya te debería funcionar bien.


PD: Esto que te comento es para PS3, para PS4 o Vita, ni idea.