Okay, here's the situation: Exchange 2010 (new installation) migrating from Exchange 2003. The clients are mostly on Outlook 2010 and using it in cached mode. When new users are created, they do not show up in the Global Address book.
The first part in troubleshooting this found that the user showed up in the GAL in OWA and iPhones. Further investigation led me to discover that when the user was taken out of cached mode in Outlook 2010 that the entries showed up correctly in the GAL. So the problem I discoved was actually in the Offline Addess Book.
After checking numerous things like test-OutlookWebServices to see what the location of the OAB was and checking permissions on the OAB folder on the exchange server, I discovered that the web.config file in C:\Program Files\Microsoft\Exchange Server\V14\ClientAccess\OAB was the issue. I renamed it web.config.old and users were once again able to download the OAB in cached mode.