If I may add my two cents:

When looking back at the reputation Marius would enjoy many years after his death, one must remember that he was a populares - a man of the people. As a Tribune of the Plebs, he was a bit of a reformer, passing a law concerning voting that made it somewhat harder for men to bribe the regular, every-day citizens during elections. As Consul, he pandered to the crowds by letting the capiti censi into the armies (of course, this was also due to the great defeats suffered in the era leading up to his consulships that had wiped out the traditional, propertied manpower of Rome).

This alone would make him quite favorable to the regular citizens and inhabitants of Rome. Add to that his victories over the Africans and Germans, and you do indeed have yourself a genuine folk-hero.

Then along comes Sulla - a reformer, but not like Marius. He wants the Republic to be like it was long ago - and curtails quite viciously the powers of the Tribunes, the people's magistrates. He was everything that the people didn't like. This, I believe, only served to enhance Marius' reputation, after the both of them were dead.

LVF