According to the Director of PlayStation Network Operations Eric Lempel, PlayStation Portable Firmware Update 5.01 is coming soon.
To quote: PSP firmware update 5.00
added direct access to the PlayStation Store, and we’ve since found an issue related to larger-capacity Memory Stick PRO Duos, which we’ll be addressing with a new update (5.01).
When downloading content from the Store to a PSP with an 8 GB or 16 GB Memory Stick Duo media inserted, you may see a message indicating that the media does not have enough free space, even when sufficient space exists.
Update 5.01 resolves this issue and will be coming soon. More PlayStation 3 News...