Just in case anyone else is having an issue similar to this and has tried several things like I had... I was able to resolve the issue by opening up the exchange management command shell and using the following command.

Update-OfflineAddressBook “Name of Address Book”

Re-downloaded address book after wards and voila!