I'm not sure Brahms was as unoriginal as you make out. In any case, his style is certainly no older than (say) mid-to-late Beethoven; Beethoven died in 1827 and I'm pretty sure that when Brahms was born in 1833 mid-to-late Beethoven wasn't "out of style" in any useful sense.

J S Bach's music was widely regarded as old-fashioned in his own lifetime, but if anyone's canon[1] he is.

Saint-Saëns was born later than Brahms but his music isn't any more "modern" than Brahms's, and he was both popular and well regarded by critics (not as well regarded as Brahms, but that's perfectly well explained by his not being quite as good).

[1] Pun not intended but deliberately left in once noticed.

I think the following is perfectly credible and consistent with Brahms's success:

• To be regarded as a great artist, one must do impressive things.
• Great skill is impressive. So is great novelty, at least if accompanied by sufficient skill.
• So famous artists will tend to be skilled and original, but the exact proportions of skill and originality will vary.
• Brahms was exceptionally skilled and (for a first-rank composer) relatively unoriginal. In comparison, e.g., maybe John Cage was exceptionally original and relatively unskilled.
• That's all.

There's really only a puzzle if you insist on saying that success generally has nothing to do with skill, which sounds impressively cynical but really doesn't seem particularly likely to be correct.