Your understanding of keys is about right. It is the OP article that your are not understanding.
You ask "so how can the NSA decrypt such a message?" That's what the article is telling you: Either by 1) getting the private key from the corporation you are communicating with, or by 2) cracking the cryptography.
Most people don't encrypt every email, they just use https to their email server. You say you're not sure about https, but that is the big vulnerability. So NSA just needs to ask your emailserver corp for their private key (to decrypt the packets, and then everyone can deny that the NSA obtained your email from the corp). This is case 1) above.
For people who encrypt the message end to end (as in your example "encrypt a message to someone I need to use that person's public key"), this is case 2). It is controversial whether the NSA can crack the best ciphers, which are postulated to be near-impossible to crack. But the NSA has resources we cannot imagine and/or secret resources we cannot even know about. When the first encryption schemes came out, they were strong in the day but were later brute forced by more power computers. So there are some who think the NSA can or will be able to crack the current crypto (that's what the OP is referring to when he says "the means to subvert widely used mechanisms"). As others have said, in targetted cases like this, it may be easier for the NSA just to plant a bug on the receiving computer, to read contents after it has been decrypted.
Now certs, which you have half wrong. Yes, certs give confidence that you have the correct public key. But certs are mostly used by companies (case 1 above) not individuals (case 2).
In case 2, peer-to-peer encryption, individuals rarely go to the expense of getting trusted certificates. You say "let's take this private", and you send him your public key, or he sends you his--no cert involved. Instead you both rely on publishing your public keys everywhere and all the time (at the bottom of every email, on their website, etc.). That provides some history for you to trust the key he sends you--and vice-versa. In other words, public keys MUST be displayed publicly before you want to use it to gain credibility.
Certificates are a way for companies to publish their public key with a credible certificate authority (CA). A certificate is essentially another public-private key pair that lets you determine that the CA really endorses the public key you are interested in. The credibility of the CA is determined by their record in the marketplace as to whether they endorse credible companies and whether they keep their master keys secure.
The original article really doens't address certs, except to say that if master keys can be deciphered, we cannot trust certs anymore. That's because a malicious party could create a cert that looked real but wasn't (this happened recently when somebody stole one of the master keys used by a CA--they were able to make fake certs).
My question to you is: if you misunderstood the article, why are you taking such strong positions in your other comments?