Thanks for the follow-up. My personal belief is that Tillman Jr. was Tillman Senior's son. Largely because 1) the 1880 census enumerates him as such and 2) Sally Brown must have felt VERY strongly to name her child after a man, despite his objections that he had had nothing to do with her.
I'm still looking for more information on Sally Brown. I have seen her connected to Junior in countless family trees and I don't know what the source is for that information. Possibly family lore, or is there a birth certificate out there for Junior somewhere...?