A telecommunications carrier shall not be responsible for decrypting, or ensuring the government’s ability to decrypt, any communication encrypted by a subscriber or customer, unless the encryption was provided by the carrier and the carrier possesses the information necessary to decrypt the communication.
Note "unless the encryption was provided by the carrier." Skype is the one that provides encryption here (a carrier) as far as I understand. No user can influence it. You are right that they are allowed to make the systems where users would provide keys themselves and that then the carrier wouldn't be required to assist in the decryption.
There's readily available examples of crypto software generating key pairs on the client end, and never exposing the private key to the server - GPG/PGP, OpenSSL, tarsnap - and the OpenSSL libraries are used by a whole bunch of other software too (encfs, browsers, web servers, CSR generation…)
Any "crypto" which doesn't do secure keygen on the client for "at rest" data storage is now significantly more suspect than before these revaluations. You can explain away whatever you like in terms of "usability" or "most users don't care", but now manyof us are going to read any excuses as "Yeah, the US government has got to our CEO… And he's not gonna be the next Qwest guy…"
Which is just a way of saying "we don't require you to do what you can't do." A truly good service would take advantage of that by ensuring they themselves have no access to the communications.
Note "unless the encryption was provided by the carrier." Skype is the one that provides encryption here (a carrier) as far as I understand. No user can influence it. You are right that they are allowed to make the systems where users would provide keys themselves and that then the carrier wouldn't be required to assist in the decryption.