If this was a server migration from 2003, try running this command in the Exchange Command Shell:
New-OfflineAddressBook -Name "New OAB" -AddressLists "\Default Global Address List" -Server EXCHANGE -VirtualDirectories " EXCHANGE\OAB (Default Web Site)"