I just started getting the same error last week when doing 'Full access' permissions through EMC. Roll-up 4 has been installed for several months, The only change i've made this week that i'm aware of is installing Sophos' PureMessage. Have you found a solution?
Edit: Well nevermind! I rebooted the server, but it looks like the 'Recipient picker scope' is a little buggy, I need to let the whole forest populate before I search for a user or edit the search scope with the picker. I'm changing the default Scope now, thats always bugged me! Oh well, good luck