From the article:
NC Soft said it was not clear how the user IDs were stolen, but given the scale of the fraud it speculates that a major portal site or community site was attacked by hackers.
An NC Soft staffer said the fraudulent users created game characters for themselves with stolen ID numbers and names and paid for membership via mobile phones that were also registered with stolen names. The firm is investigating to establish the exact scale of the damage
One clue points to China, because many of the fraudulent users use Chinese names like Xi. There have been warning signs for several years. A staffer with an IT security firm says several hacking programs designed to steal private information from various Internet sites went around last year, and there have been several attempts in China as well as Korea to steal private information online.