Go to this site: http://www.accessgenealogy.com/native/finalroll.php
and do a seach on your surnames. You will find both Melton and Walton listed on the last page of each as Creek and as Freedmen. Freedmen were the former black slaves of the Creek. This scenario seems to fit into your family so perhaps we finally have a grandmother who is correct!
The only way you'll know whether you connect to any of these names though is to do your genealogy backwards, starting with yourself and connecting each generation (parents, grandparents, ggrandparents, etc.) through actual records, i.e. birth, death, marriage, census, etc.
If you have any further questions, I'll try to answer them or I'm sure someone else will.