I'd say it's the memory card. 3rd party memory cards are pretty unreliable, and there have been many reports of 3rd party memory cards not working. I've never seen "memory card not formatted" on my PSone, but if you format it and it still doesn't work, then there's obviously a problem with the card.
Hope you didn't have too much saved on there...