PSP v5.01 Update
PSP firmware update 5.00 added direct access to the PlayStation Store, and Sony has since found an issue related to larger-capacity Memory Stick PRO Duos, which will be addressed 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," said Eric Lempel, Director, PlayStation Network Operations.