По мне так чем проще – тем лучше. Линейный рост, имхо, меньше вопросов вызовет

По-моему, начисление score уже достаточно нетривиально, чтобы вызывать вопросы у тех, кто пытается понять, как оно работает. Собственно, я вообще считаю, что пользователям достаточно просто знать, что чем больше звёзд, тем дольше будешь добираться до следующей — понимать механизм работы необязательно. В профиле рядом со score отображать количество, при котором появится следующая звезда. Т. е., например, 350 / 500. (При наведении на 500 показывать поясняющую надпись.) Любителям “игоря” такой принцип должен быть вполне знаком. Для любознательных где-нибудь на FAQ-странице привести вышеуказанную таблицу и описание алгоритма. Если что, я лично готов объяснять, как оно работает, всем, у кого возникнут вопросы.

Может лучше сделать звёзды разноцветными?

Мне такая идея не очень нравится, обилие цветов слишком перегружает информационный фон. Всё-таки цвета лучше использовать для выделения информации, а не как отдельную смысловую единицу. (Тут ещё стоит учитывать существование разных тем и пользовательских стилей.)