Once AD Replication completes (could be quick or a long time depending on your environment), the OCS Address Book Service (ABS) needs to pick up the changes. The ABS sync process runs at 1:30am each day. You can force this by running abserver -syncnow from the /Server/Core/ folder of your OCS server install. Finally, the new address book is downloaded when the client logs in and discovers a new address book file.