If you add a new mailbox or a distribution list to your Exchange 2010 server you need to either wait for the address lists to update you can force them to update.

In the Exchange management prompt run:

Get-GlobalAddressList | update-GlobalAddressList
Get-AddressList | update-AddressList
Get-OfflineAddressBook | Update-OfflineAddressBook

On the Clients you might need to update the Offline Address Book by going to Send/Receive – Send/Receive Groups – Download Address Book…

/Johan