Calls to PlayStation support lines have left the users frustrated at the seeming lack of a solution. Constant days of "research" on their part seems to suggest only one solution: returning the system for a new one. We haven't encountered issues with the Store on our end, but we also don't manage more than one license at a time per system. A word of warning: don't deactive your PSP systems unless you really mean it! And don't try having multiple licenses (from different territories, for example) on your system.
We wish the best of luck to those affected, and hope to have an update regarding their situation in the near future.