Sensible idea, but in the UK you can be forced to tell the court your password. So if you were ever accused of something they could get the private keys of everybody in your address book and decode all your past traffic.
Anyway, they can't store that much data, and they are not actually proposing to: "databases would not record the content of the customerâ(TM)s communications but would store the numbers and email addresses of the sender and the recipient and [...] Facebook communications".
So really the encryption does nothing in this case. If they don't have the content, they can't decrypt it either. Even if it's encrypted they would still have your contact lists. Encryption wouldn't even be an option for Facebook messages, I would think. You could simply switch to Google+, or use "https" for Facebook. However these social networks would obviously still have all the messages stored, and a court could mandate that you hand over the password to the account.