injustice, beginning with Jesus and ending with Mandela, has become immortalized in the popular imaginary. 

With the passing of time, such characters are enriched by mythical feats they may not have accomplished. This is how ordinary men vicariously fulfill their dreams of grandeur. 

In one way or another, we all have suffered some form of oppression by different regimes. Very few of us have dared to actively oppose it. We tend to find comfort in those who have resorted to the sword, the pen, or passive resistance (e.g. Gandhi). 

The fact that the cinema and the television have so often found Sparacus's story attractive has contributed to his "immortalization". Other, similar characters, like Vercingetorix, who fought Roman domination in Gaul to the last consequences, do not enjoy the same recognition from the layman. 

Thus, probably another factor to bear in mind is the extent to which a given character is made known to the public by the media. I do not think people would remember Spartacus if they had only read about him in a school text book describing the Third Servile War against the Roman Empire. I also doubt that many know that Marx listed him as one of his heroes. 

Actually, I think any kind of controversy will help immortalize a person.  However, in Spartacus’s case it is his interesting story that keeps people interested for so long.  Any time there is both an interesting story and a controversy, a person is likely to stick in people’s minds for a long time, proportionate to how interesting the story is, I think.  We also have a fascination with the era, and that certainly helps.