I received this same message the other day, and I thorougly researched the Playstation website and elsewhere on the net for more information. Here is what i've learned in a nutshell...
Each Playstation 3 system can have a maximum of 64 accounts per the life of the system. There is not way to delete, or otherwise disable these accounts without contacting technical support. I read several testimonials from folks who dared to call technical support to have their PSN accounts reset, and they claim that they were virtually accused of being theives, and were threatened with lifetime bans. Again... i have not tried to call them firsthand, but apparently, the PSN account limit has been in place since the PS3 was developed, and once used, can only be undone by technical support. What I would be interested to know is whether the PSN account information is tied to the system's MAC address, or whether there is a file kept on the hard drive. My guess is that the machine's MAC address is logged with the Playstation network, so a hard drive swap would likely be ineffective to reset the PSN limit back to zero.
If anyone else has tried to contact technical support, I would love to know what they are saying since the birthday exploit.