When you restore the phone, do not select the phonebook,. The phone is most likely pulling addressbook information from your email environment and the restore is apppending new “duplicate” data.
his is what I had to do when we migrated from Exchange to Domino. After the first 3-4 phones, I just skipped the restore portion. There was no need to restore anything since we use roaming profiles in Domino and the user has access to their Notes address book via BES.