So, Sony has admitted that they screwed up in Firmware 5.00 for the PlayStation Portable. Though they included the PlayStation Store and direct downloads, there happens to be a glitch when people using high-capacity Memory Sticks (mainly the 8GB or 16GB cards) were being reported as being full, when they were really lots and lots of free space in them.
Sony has said that an issue will be coming soon. Oh great!