How would have they distributed the keys? I can easily upload a key with an arbitrary id and username to any public keyserver. You have to actually check that you trust the key by utilizing the web of trust.

Alternatively, you could use SSL certificates, but since the attacker controlled cyanogenmod.com, he probably could have social-engineered the CA to issue him an email certificate.

Trust is hard.