dyoung, you can look at this blog for your permissions: http://blogs.msdn.com/dgoldman/archive/2007/05/16/missing-permissions-on-the-address-lists-container-breaks-the-oab-generation-process.aspx
None of your permissions should have changed at all. You might want to consider turning up logging for MSExchangeAL and looking at your address list synchronization to see if the users are being added to their address list. You can also look at the showInAddressList attribute to see how many they are a part of and it should be the default offline address list and their company. If they make a query to the default it will fail and should roll over to their company. Make sure your groups are set up correctly.