Hello, first of all, tout nouveau tout beau is NOT a proverb.
It is rarely used as a complete sentence with a general meaning, and the meaning is rarely the implication "that which is new, is pretty".
Therefore, the "new broom" proverb is only valid in very specific contexts, and the novelty wearing off phrase is only valid in negative contexts.
Actually, this phrase just means that something is all shiny and brand new.