I'll give it a go.
I'll start with providing an extended quote from Levin's dialogue with Oblonsky:
'Aristocratism, you say. But allow me to ask, what makes up this
aristocratism of Vronsky or whoever else it may be - such
aristocratism that I can be scorned? You consider Vronsky an
aristocrat, but I don't. A man whose father crept out of nothing by
wiliness, whose mother, God knows who she didn't have liaisons with...
No, excuse me, but I consider myself an aristocrat and people like
myself, who can point to three or four honest generations in their
families' past, who had a high degree of education (talent and
intelligence are another thing), and who never lowered themselves
before anyone, never depended on anyone, as my father lived, and my
grandfather. And I know many like that. You find it mean that I count
the trees in the forest, while you give away thirty thousand to
Ryabinin; but you'll have rent coming in and I don't know what else,
while I won't, and so I value what I've inherited and worked for...
We're the aristocrats, and not someone who can only exist on hand-outs
from the mighty of this world and can be bought for twenty kopecks.
'But who are you attacking? I agree with you,' said Stepan Arkadyich
sincerely and cheerfully, though he felt Levin included him among
those who could be bought for twenty kopecks.”
It is important to note that Levin says the above while being offended by the fact that his proposal was turned down by Kitty Shtcherbatskaya (or, rather, by her mother - as Stiva tries to reassure him), and the higher social status and the wealth of Vronsky was presumably the main reason.
Levin here outlines his personal view on what he considers to be "true aristocratism" and this view is a bit idealistic, with the stress on 'honesty', 'reputation', 'education' and the independence "from the mighty of this world".
So, to comment on your specific questions:
Wouldn't that reputation be a huge problem in Russian society of the time, by itself enough to lower Vronsky's social status below that of Levin?
No, not really. A few idealists like Levin might have despised you but as long as you're rich and stick to the aristocratic life style (banquets, balls, duels, etc) you'd be surrounded by crowds of people looking up at you. Besides, it was his mother whose reputation was questionable, not him.
Also, I would assume that lineage would be crucial to aristocratic status, so how can Vronsky's family be considered very noble if they can't trace four generations back?
We don't, actually, know about the lineage, Levin speaks about "three or four honest generations in their families' past" but, as I said, this view wouldn't be shared by many.
And what of the description of Vronsky's father as a man who "crept out of nothing by wiliness"?
Tolstoy never explains what exactly is meant by "crept out of nothing by wiliness (in other translations: by intrigue)" in regards to Vronsky's father (at least I couldn't find anything on this), so we are left to make any sort of wild guesses. I would assume that Vronskys are a noble family in many generations but only his father somehow managed to creep into the "top of the tops" and acquire great wealth.
Anyway, apart from Levin, everyone else refers to the de-facto aristocratism of Vronsky - he is a Count, very rich, graduated from a very prestigious military school and so on.
Updated:
In a way, you can see it as two different meanings of the word aristocrat being used here and the difference is somewhat similar to the meaning of "gentleman" in English as outlined here:
For most of the Middle Ages, when the basic social distinction was between nobiles (the tenants in chivalry, whether earls, barons, knights, esquires, or freemen) and ignobiles (serfs, citizens, and burgesses) the word gentleman was roughly equivalent to nobilis.
In this sense, Vronsky is definitely an aristocrat.
Levin, however, refers to the moral aspects of what he calls the real aristocratism, as in (from the same source):
In general, however, the modern "gentleman" is well mannered rather than necessarily well bred or well off.
Hope this helps.