The CDO patch messed up "send as" permission on mailboxes. What are we doing wrong?

Q: We deployed the CDO Patch and it messed up the "send as" permission on all the mailboxes. Lots of TREO issues on Monday morning we had to go back and adjust permissions to get it to work. What are we doing wrong?
A: Please take a look at KB article 912918 on the Send As issue.