The celebrities' passwords weren't changed - their existing passwords were brute forced. This was possible because (until this past weekend) Apple didn't restrict the number of password guesses being tried against an account. And once the hackers had the passwords, they were able to do a "restore from iCloud" to a faux new device, using that supposed law enforcement software from Elcomsoft - a step that does not currently require two step verification.
Two step verification is a good thing. Apple definitely should expand it. But it's not a panacea for every ill, and there will be situations where it's not practical. It's going to be hard to implement, for instance, when the user only owns an iphone and nothing else.