Bennyben, just to let you know m8 that this error can also appear if you're using a fake memory card - took me a while to find out!!
If if you choose the memory card under game and then hit the triangle button, choose "Information" and it will show if the card is "supported" or "Not supported".
If "not supported" then a 99% chance it's fake bud.