Why don't you enable broadcast of enc capability by default?
Assuming this is a security concern of users being too trusting, you could just popup some kind of alert whenever a new key is assigned that I think would fix any problems of trust. As far as privacy implications of 3rd parties discovering you were using encryption, I can't really think of any.
The people who would usually care the most would be local sys admins or others with the power to sniff your data anyway. So they'd be able to notice you're encrypted traffic IM and discover it that way.
And let's worry about AOL blocking this once we actually have more than 50 users.