The term "Subsaharan African" is a little bit racist. It was invented by Europeans to suggest that there is some type of invisible barrier that seperates the Saharan peoples from the peoples who lived south of the desert. There isn't really a boundary where people suddenly jump from "Berber" to "Negriod" but it is more of a melange. If you go into desert villages in Tunisia you can often find people who would qualify as "Negroid" and if you see the Touregs of Mali you will find some who have light complexions and "European" features (Of course it becomes more and more rare as you travel south.) The Saharan peoples interacted quite often through trade and naturally this contributed to the mix of ethnicities that you can find in Northern Africa.

I have no doubt that many "black Africans" made their way into the Legions. Read the story of St. Maurice for example. He lived during the time of the late empire and was a black man in command of an entire legion. :)