I am on Kmeaw 3.55 if that helps.
What you will need:
Have F**PSN or another method to connect.
This is ALL done via the PS3, however with backing up save games theoretically should be able to copy and restore these with filezilla or similar.
Step 1: Backup your save data with an external drive (note, some may have copy protection and cant be copied).
Step 2: Delete the PSN account that has the error
Step 3: Create a new user
Step 4: Go to Sign up for PSN account
Step 5: Restore existing PSN account
Step 6: Follow the standard prompts
Now I can download all of my purchased content again.
Note: I did deactivate my PS3 through the account management section on the XMB first but you may not need to.
There are other tutorials that tell you to format your HDD or quick format, its not needed. Well not for me anyway and it took only 5 minutes.