Problema al acceder a la Store

Recientemente me ha pasado algo muy raro y no encuentro cómo solucionarlo, a ver si alguno podéis echarme una mano:

Tengo la PSP fat con el firmware 5.00 m33-6 de Dark Alex; me cree una cuenta en la Playstation Store hace poco y siempre he podido entrar sin ningún problema, incluso me he podido bajar contenidos para algunos juegos.
A raiz de un problema con mi Memory Stick y unos datos que se me corrompieron, he tenido que formatearla [FAT32]. Ahora, al intentar acceder a la Playstation Store me dice:

Se requiere una actualización del software del sistema de la PSP. Para métodos de actualización, consulte las instrucciones del sistema PSP

Antes de formatear la Memory Stick, obviamente, he guardado en el disco duro todo lo que había en la tarjeta [ya en el HD pude borrar los datos corruptos, un par de partidos] y luego lo he dejado todo tal y como estaba... pero nada, no hay forma de entrar.

¿Podríais decirme alguno qué ha pasado? ¿Habré perdido algo que no debía perder? Lo único que borré eran unas partidas de la carpeta SAVEGAME, así que en teoría no debería haber tocado nada de más...