I hate to get involved in a debate like this, but at least one poster said that the costumes should have been a warning sign. The problem there is that the costumes were Persian/Arabian in style, not sub-Saharan African. I think the director was possibly going for a mix of ethnic influences (add in the references to Native American culture and a Chinese dynasty, IIRC).
So all I'm saying here is that the costuming wasn't stereotypical of the racial type that was being cast. Don't shoot me.