Castrofobia, I emailed Playstation Consumer Services, and they got back to me with this:
'I recommend downloading a free demo that is about 1000MB. Once the download has completed, you can then delete the download and try playing your game once more.'
I tried it, to no avail. You should try it on your system though, who knows, perhaps you'll get lucky. The email also said to email them right back if it did not work, so I have done that, and I am waiting for further instructions. If there's any consolation in this nonsense, it's that we are not alone (there seems to be a really small number of people who have posted on a couple of forums about having this problem). Here's to us finding a solution.