Grading of the chain: Its chain is "very weak".
Technical note: Abd al-Rahman bin Abd Allah al-Umari is "matruk" (abandoned), and he has been corroborated by something that does not establish proof. Al-Dhahabi declared it defective for this reason in "al-Talkhis" and said: "Abd al-Rahman is saqit (worthless)."

Reference / Source: Al-Khara'iti narrated it in "Masawi' al-Akhlaq" (417) and al-Ajurri in "Dhamm al-Liwat" (28, 31) via Ya'qub bin Muhammad al-Zuhri, from Abd al-Rahman bin Abd Allah bin Umar, with this same chain.

Reference / Source: Ibn Majah (2562) narrated it via Asim bin Umar bin Hafs al-Umari, and Ibn Hazm in "al-Muhalla" (11/383) via al-Qasim bin Abd Allah bin Umar al-Umari; both of them from Suhayl bin Abi Salih, with this same chain.

Criticism and details: Al-Qasim's narration has the wording of "killing", not "stoning". Asim bin Umar al-Umari is agreed upon to be weak, and al-Qasim bin Abd Allah is "talif" (ruined, extremely weak), and Imam Ahmad accused him (of lying). After hadith (1456), al-Tirmidhi pointed to the hadith of Asim and said: "This is a hadith whose chain is criticised, and we do not know anyone who narrated it from Suhayl bin Abi Salih other than Asim bin Umar al-Umari! And Asim bin Umar is considered weak in hadith because of his memory." Ibn Hazm said: "As for the hadith of Abu Hurayrah, al-Qasim bin Abd Allah bin Umar bin Hafs is alone in it! And he is discarded, utterly worthless."

Analysis and correction: In Ibn Hazm (11/384) one chain of this hadith occurs as: "Ubayd Allah bin Rafi', from Asim bin Ubayd Allah, from Suhayl bin Abi Salih." We think this is a corruption of "Abd Allah bin Nafi', from Asim bin Umar", especially since it is from the narration of Yunus bin Abd al-A'la from Abd Allah bin Nafi', who is Ibn Majah's shaykh for it.