I've read in multiple places that it is important that your recommenders be known to the admission committee. If I were to have a letter of recommendation from a professor who is quite new (Assistant Prof), would their recommendation be discounted due to their lack of reputation or stature in the field?
An unestablished professor that knows you well, and writes a fantastic letter, is far better as a letter writer than a famous professor that will just write a generic "he was 3rd out of 38 students in my class" kind of letter.
There are two types of letters that will really help you in general. (1) A great letter from a professor who knows you well, regardless of their stature. This is likely someone you did research with, and (2) A famous professor that will write you a decent letter, saying you did well in his her/class and you show real potential, ideally you should have done a class project for them, so they can say something beyond basic things like class rank. Letters of type (1) are the most important (if the professor is famous that is a bonus). But you need 3 letters usually, so you are not likely going to have 3 professors that know you well (if you do you are in great shape). Type (2) is another good option for filling out 3 letters. If all your letters are of type (1) and (2) that is a really good sign. Most people will have at least one lackluster letter from an unestablished professor.
The next best bet is an unestablished professor that you did a good class project for or knows you well from a class. Generic letters really do not help your cause.
As you said: Someone who is well-known is a good choice. If the new professor already has a good reputation in her field, it will most probably be a good decision to ask her. It's better to have a letter of recommendation from someone who knows you and who writes somethong personal, than a letter from someone just looking at your marks.