I don't think we have enough information to assert that our non-Horner Subsaharan ancestors spoke Nilo-Saharan. Another convincing guess is to say the Ancestral East Africans spoke a dead language that may or may not have been related to proto-Nilo-Saharan. Or even more radical, the Ancestral East Africans could have had an ANA-rich component and spoke some dead language related to AA. But hey, why let the imagination stop there? What if they spoke something that was linguistically antecedently equidistant, giving good resolution to place a linguistic relatedness between the two families. Who knows, man?
For example, I speculate that Sumerian, a classified language isolate derived from the nature of pre-agricultural revolution people relic of a hunter-gatherer origin that carried the particular type of speech signature. I think, and as we see with the processes of history and pre-history, we have a strong reason to believe as hunter-gatherers were very genetically differentiated relative to proximity when you compare it to today, there was a linguistic richness in diversity. Today you see the opposite. Homogeneity with proximity and wide distribution of a set of linguistic families.
In theory, the existing classified language families are daughter languages of older and wider linguistically genealogical phylogenetic structures that of which the far majority of branches are dead ends, and it reaches so far back that we have no way of accurately getting a refined sense of orientation like the comparative method can conceptually inform us about to what degree post-agricultural internal branches within a family relate both laterally, representing something like time-depth/divergence, and width, representing the degree of similarity.
Afro Asiatic is then a very successful line that became a wide tree (even going beyond the comparative method in the earliest layers, a valid testament of its age), but in the advent of this lineage, to say that a few related lineages survived is not far-fetched to me. So yes, our ancestors might have spoken an AA-related language, or if the depth of relatedness was too high temporally, we would have registered it as an isolate, a patch, the remnant of a dead structure that AA was a part of.