First off, do you have the latest firmware? There was an issue with the playstation store not reading the correct available free space on 8 and 16 gb sticks.
Do you have a memory card reader? If so just put the new stick in your psp and transfer everything from one stick to the other. I have done this several times with no problems.
I was searching for a solution to what seems to be a very old problem, as I've recently come across this error too (I've never downloaded a game off PSN until now). The official forums are shockingly unhelpful, and support never seems to read the entirety of their received tickets. I was trying to redeem my copy of Yggdra Union, and I would hit the error (which isn't in their database, by the way - ???) after the download and during the installation. I then tried completely shutting down my system and trying the download again. This time it worked without any problems. Maybe the installation doesn't get along well with "sleep mode". Anyway, hopefully this tip helps people that come across this in the future.