Hey there, DemonDSi! This seems to be that you are out of memory on your memory card, but that also seems unlikely as well. What backup are you trying to use? What model PSP do you have? What type of memory card do you have (make/ model) and what custom firmware are you on currently?
As Kittymat says, formatting the memory stick will create the folder for SAVEDATA, but if you'd ever formatted the memory stick before, that folder should already be where it needs to be. Alternatively, be warned, as formatting will delete all data on your memory stick so take precaution to backup necessary files first!
The second idea that come to mind about your problem is that you may have a fake memory card or a larger capacity (and slower) Sony brand memory card. Do you have another memory card you can test with or a friend who has a memory stick from say, Sandisk? Sometimes Sony cards have slower read/ write speeds, especially the higher capacity ones (4gb+) and that can lead to poor emulation for homebrew that need to load often like Nintendo 64, PS1, and PSP game backups.
If you're unable to be helped in this forum further, I encourage you to click the picture in my signature. You'll be taken to PSPBrew.com - where people are more specialized in this sort of thing.
-DarkPacMan77-
