Que cosa mas rara...
Bueno primero tienes que aclarar en donde compraste la Memory Stick, porque segun donde la hayas comprado, te puede haber tocado una Memory Stick falsa. Para averiguarlo, es facil si tienes el firmware 3.00 o superior a el. Simplemente te vas al apartado de Juegos y le das a "Triangulo", y posteriormente a informacion, si te sale "No compatible con Magicgate" es que te ha tocado una Memory Stick falsa.
Es la unica posibilidad que se me ocurre, aunque tambien podrias probar a formatearla desde la PSP, para ver si asi se soluciona el problema.
Lo que tambien podrias probar es, ver el tipo de formato que tiene, y si no es el que deberia, cambiarlo, formateando la Memory Stick desde el PC.
Saludos.