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