How about rating of rating?
I mean to make votes of those who is with high problems solved rating more important.
Try this sample as very simple implementation. Let consider we have two players: Absolutely Begginer (1%) and Medusa (52%). Begginer rates someone's VeryGoodProblem just with "1", but experienced player thinks it's "5". Resulting rating is 1*0.01 + 5*0.52 = 2.61. Heh, for two voters and my dull implementation it even smaller than (1+5)/2, but it was just to understand the conception. For real working system result may be achieved as ( ("1"*0.01 + "5"*0.52)/(0.01+0.52) ) = 4.92. So you see, voice of experienced player gives the basis of the rating. And, by the way, I don't think there's really a need to update ratings of the problems throughout changing of voted players experience, because their opinion was fixed at the moment of voting, but in this case players must have an ability to revote for the problem due to the same reasons.
I don't know exactly how it was at the moment of the creating of this topic, but now interface of a single problem page may be simply overloaded with additional "Quality label voting", but designer should better try to improve existing system.
They might or they might not - you can never tell with bees. Vinnie-The-Pooh.