Khaythamah bin Abd al-Rahman narrates this statement from his father: I came to the Prophet (peace and blessings be upon him), and he asked me: What is your name? I said: Abd al-Uzza. The Prophet (peace and blessings be upon him) said: Rather, you are Abd al-Rahman.
Al-Tabarani recorded it, and al-Bazzar recorded something similar, except that in it the words are: The Prophet (peace and blessings be upon him) asked: What is your name? I said: Aziz. The Prophet (peace and blessings be upon him) said: Al-Aziz (the Mighty) is Allah Almighty. The narrators of al-Tabarani are the narrators of the Sahih.
Hadith Referenceمجمع الزوائد ومنبع الفوائد / كتاب الأدب / 12850