Khaitamah narrates from his father that in the time of ignorance, his father's name was Aziz, which the Prophet (peace be upon him) changed to Abdur Rahman.
Hadith Referenceمسند احمد / مسند الشاميين / 17604
Hadith Gradingحکم دارالسلام:حديث صحيح، وهذا إسناد حسن
It is narrated from Hazrat Abdur Rahman (may Allah be pleased with him) that the Prophet (peace and blessings of Allah be upon him) said: The best of your names are Abdullah, Abdur Rahman, and Harith.
Hadith Referenceمسند احمد / مسند الشاميين / 17605
Hadith Gradingحکم دارالسلام:حديث صحيح، وهذا إسناد حسن
It is narrated from Khaythamah that his father, Abdur Rahman, went with his grandfather to the service of the Prophet (peace be upon him). The Prophet (peace be upon him) asked his grandfather, "What is your son's name?" He replied, "Aziz." The Prophet (peace be upon him) said, "Do not name him Aziz, rather name him Abdur Rahman." Then he said, "The best names are Abdullah, Abdur Rahman, and Harith."
Hadith Referenceمسند احمد / مسند الشاميين / 17606
Hadith Gradingحکم دارالسلام:حديث صحيح، لكن ظاهره الإرسال، وجاء موصولاً
It is narrated from Khaythamah that his father Abdur Rahman, along with his grandfather, presented themselves in the service of the Prophet (peace be upon him). The Prophet (peace be upon him) asked his grandfather, "What are your sons' names?" He replied, "So-and-so, so-and-so, and Abdul-Uzza." The Prophet (peace be upon him) said, "He is Abdur Rahman." Then he said, "The best names are Abdullah, Abdur Rahman, and Harith."
Hadith Referenceمسند احمد / مسند الشاميين / 17607
Hadith Gradingحکم دارالسلام:إسناده ضعيف، حجاج مدلس، وقد عنعن، وقع قوله: زياد أو عباد بالشك فى الاسناد، الراجح فى هذا الإسناد عباد
It is narrated from Khaythamah that a boy was born to my grandfather, and he named him Aziz. Then he went to the service of the Prophet (peace be upon him) and said that a son has been born to me. The Prophet (peace be upon him) asked my grandfather, "What name have you given him?" He replied, "Aziz!" The Prophet (peace be upon him) said, "Name him Abdur Rahman." He was my father.