They would still have been able to compromise his iCloud account and thus destroy the data stored on his computers.
Unfortunately, I think that in this particular case, having two-factor auth on GMail wouldn't have helped. His account was compromised by having a password recovery email sent to his iCloud address. Presumably, password recovery bypasses two-factor auth.
In this attack and the earlier CloudFlare attack, the attacker took advantage of inappropriate recovery email settings. While it's reasonable for consumers to enter recovery emails, I think that professionals should avoid enabling them. When a @gmail.com sends recovery mail to @me.com (or vice-versa), the attack surface is greatly increased.
Secondly, the Wired article made this claim: "Because I didn’t have Google’s two-factor authentication turned on, when Phobia entered my Gmail address, he could view the alternate e-mail I had set up for account recovery. Google partially obscures that information, starring out many characters, but there were enough characters available, m••••n@me.com."
I don't know for sure whether that's true or not. But assume it is true. If two-factor authentication had been enabled, then the hackers would have had a much harder time guessing Mat's email address for iCloud and whether he had a @me.com email address at all.
Gmail was not really needed to guess the name at @me.com.
Moreover, in his case, it seems he would be better off not having the secondary e-mail address for recovery at Google. It turned out to be anti-security measure.
I disagree. I think most iCloud users (%80 of iOS users by Apple's count) have @me addresses when they upgraded to iOS 5 or Lion. I can use both my @gmail.com and my @me.com in App Store to purchase, or to login to icloud.com.
The problem may be that "me.com" is so short that Google might display the full domain name. If that's the case, Google should fix it.