My guess would be that they found someone an address of someone with ties to a celebrity, compromised their account through security questions, and then found more personal information and iCloud accounts by going the contacts of each person they compromised.

That was my suspicion from the start, security questions tend to be the easiest way to compromise accounts since finding someone's mother's maiden name isn't hard to do anymore.