During the reenactment of the Romans vs Carthaginians in Gladiator (2000), we hear Maximus ask, "Anyone here been in the army?" with one fellow gladiator replying with "Yes, I served with you..." Does this mean the other gladiators know who he is, and thus the public, or at least his owner Proximo, know who he is?
Since he isn't in disguise, per se, if a former soldier wound up in as part of Proximo's company, it would make sense that he would recognize Maximus. Maximus, being a former general, could very well not have known that this man served under him. Regardless, that wouldn't necessarily mean that everyone would know.
If you remember, all of his troops are fiercely loyal to him. If he sees his former general, he knows something is up for a general to be now a slave. It's also possible he heard whatever cover story there was for Maximus to be slain or dishonored. He'd know, immediately, that something went wrong, and that, possibly, his former general could be in peril if people found out who he was.
He'd also take his cue from the fact that Maximus wasn't loudly proclaiming who he was, demanding his freedom or any kind of treatment. Being fiercely loyal, he wouldn't want to be the one who got his beloved leader killed by stupidly blurting out his name. So, he was still recognizable, but, out in a remote province, probably not recognizable on sight to anyone who hadn't seen him before, as a battle leader.