legacyExchangeDN appears in contact list rather than actual email address (Outlook 2k3, Exchange 2k3)

bear w/ me, as i'm fairly new to Exchange, but this is bizarre.  we recently dumped some old servers and installed a new cockdiesel server w/ Win2k3 & Exchange 2k3.  everything is working wonderfully except...

the global address list lists the right email addresses for internal contacts.  however, when a user is sending an internal email and they begin to punch in that other users name, AutoComplete offers up a contact from the user's contact list in Outlook.  if you right-click, properties on the name, the dialog box brings up the properties for that user and (i may be mistaken here) it seems to be an offline address (the Outlook 2k3 clients are operating in cached mode).  what i get is something that appears to be a legacyExchangeDN in the display as box (/o=COMPANYNAME/ou=COMPANYNAME/cn=Recipients/cn=JimmyS) where JimmyS is the user.  under the email addresses tab, no address appears.

now if the user selects the internal contact from the global address list, everything is gravy.  the mail is sent just fine.  when they select it from their contact list, it's returned as undeliverable.  i've tried changing the email address in some users' contact lists on the client side (Outlook) to use the global address list, and then the address is fine, but when i type in the first few letters of a given recipient's user name in the "To:" field, the closest recipient's name pops up.  if i hit enter to select it and then right-click, properties, that same old dialog box pops up that contains no information except for that legacyExchangeDN in the "Display" field under the "General" tab.

even if i had a solution to fix the Outlook clients, i'd really rather avoid that because hitting every workstation and editing all of their internal contacts wouldn't be much fun.  if that's what it takes, so be it, but isn't their a simple adjustment i can make on the Exchange Server to resolve this?

thanks in advance.