Madison E. Rhodes was born 1813 in North Carolina. He married Miriam Johnson whose parents were living in Henderson County, NC. It seems likely that Madison Rhodes was living in that same area of NC. Madison & Miriam moved to Walker County, GA. Also in Walker & Catoosa Counties I found a Joshua Rhodes living in Madison's household according to the 1870 census, and a Wesley Rhodes (who named a son Madison Early Rhodes). Do any of these names appear in your North Carolina Rhodes?
Madison & Miriam's children wer named Richard, Jerome, Hatford, Georgia Ann, Drusilla, Marvin, Talula, Correna, and Carni (?). Do any of these names seem familiar?