How about something more subtle like just a small red or yellow arrow, thin black border, or not, outlining the arrow, pointing to the right. About 2/3 as wide as the new NEW icon, and 2/3 as high at the max width of the tip, transparent background around the arrow, not in a box.

Or some other icon other than NEW. Within a couple of visits most people will know what it means, put it in the FAQ's too.