Global Address Book errors

I am running Exchange 2010.  I have a couple recently added users that are either not showing up in the Global Address Book, or replying with NDRs to my internal users.  Initially, on client workstations, we went to outlook > tools > send/receive > download address book.  This took 20 minutes or so, but eventually it seemed to fix the issue.  Now, however, this doesn't work.  any ideas?


Generating server: Mailsrvr2.domain.com

IMCEAEX-_O=CUI+20STACK_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=Mdeines@domain.com
#550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##

Original message headers:

Received: from mailsrvr2.domain.com ([fe80::64b7:35cb:ae1:7884]) by
 Mailsrvr2.domain.com ([fe80::64b7:35cb:ae1:7884%10]) with mapi id
 14.03.0158.001; Wed, 26 Feb 2014 14:01:13 -0800
Content-Type: application/ms-tnef; name="winmail.dat"
Content-Transfer-Encoding: binary
From: Bryan Free <bfree@domain.com>
To: Mark Deines <mdeines@domain.com>
Subject: test
Thread-Topic: test
Thread-Index: Ac8zPkP0T8BOdTo5RYGM7B+1o8b3qQ==
Date: Wed, 26 Feb 2014 14:01:12 -0800
Message-ID: <3F86718E3087FB47BBF765FE3496B139125780D6@Mailsrvr2.domain.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator: <3F86718E3087FB47BBF765FE3496B139125780D6@Mailsrvr2.domain.com>
MIME-Version: 1.0
X-Originating-IP: [192.168.75.x]