Well... I was hoping for quick input but there wasn't many people in the chat, nor any of you... so I was going to post here but then things ran further than I expected... so I'm just dumping all the cars from my train of thought in here.
So here is a preview with all my ideas in the order they came. O is the current stuff. 1, 2 and 3 are various TF2 reds n blues. Then a friend suggested the gray be lighter since no-new really shouldn't stand out. That led me to the idea in column 4, which bypasses the issue of contrast entirely. Finally resulting in 5 which is my preference.
So what's the opinion on 5? Any colors in 1, 2 or 3 you'd prefer instead? The CP board red would be changed to match a changed thread red. I feel all locked threads would become paddlelock-on-gray, regardless of heat level (it's locked... not like it matters).
edit 3 weeks later: guess it wasn't very important after all!