Hola, yo igual tenía el mismo problema desde la última actualización, y ya llevaba más de una semana que salía el mensaje de que la Ps Store estaba en mantenimiento.
Lo que tuve que hacer fue eliminar la PsStore y volverla a instalar.
Sólo tienes que ir al ícono del PsStore, oprimes triángulo y le das eliminar. Luego vuelves a oprimir el ícono con X y te mandará a descargar el software, son 65MB.
Esperas a que se descargue, se instale y ya con eso debe funcionar.
Si no te funciona eso, vuelve a dejar un mensaje para ver si alguien más puede ayudarte.
Saludos.